  # Recursion

Ok I have some fundamental understanding of recursion. Basically it’s a loop. What I don’t understand is for example in the following code is how does the return keep updating its calculations without refreshing itself with every loop. In other words how does it not lose its value after every iteration through itself? Also with the following code eventually the value will count down to 0 so why does it not return 0 being that the first statement is set to return a 0 if 0 is detected.

For example if I pass the value 3 as the parameter the method returns 6 which is the correct return. However after each iteration the value of the parameter is reduced by 1 eventually reaching 0. Now after it reaches 0 shouldn’t the Base case statement be processed and the return be 0?

FYI this isn’t for a school project it is for my personal understanding. The semester is over but I still feel I need to increase my understanding of how and why recursion does what it does before I am able to be comfortable with using it.
``````public static int mystery (int n)
{

if (n == 0)
return 0;
else
return n + mystery(n-1);

//The following is an exampler of what recursion looks like using a loop instead
/* int intCount = n;
if (intCount == 0)
return 0;
else
{
while (n != 0)
{
intCount = intCount  + n-1;
n--;
}
//return n + mystery(n-1);
}
return intCount;*/
}
``````
Java Last Comment
webdev2000 mrjoltcola Well that is because recursion isn't really a loop (I mean in spirit it is but not really).

A loop would be simple iteration of the same code without changing of context (stack, etc.). Each iteration uses the same variables.

Recursion is calling of same code while changing the context (pushing local vars, etc.) so each iteration uses a new set of variables (on the stack). Each call of the same function gets its own copy of the named variables.

You must do some reading on "execution context".

Code is made up of 2 things, executable instructions and context. It is the context where your different versions of the same variables are stored. mrjoltcola Call mystery(3)

Push n (3) on the stack.
Jump (call) mystery function.
mystery has 3 as a value of n

Call mystery(n)
Push n (2) on the stack.
Jump (call) mystery function.
mystery has 2 as value of n

...

Unwind of stack happens
return (pops previous n 2 off stack)
return (pops previous n 3 off stack)
..

Some languages have what is called "tail" recursion, which says if your self-call of mystery() is the last statement in the function, it allows the unwind step to be skipped (optimized away) because the function call can skip the stack manipulation since there is no more code after that statement. So if your recursion had self-called 1000 times, you would have skipped 1000 pushes to save the local value of n for the next call of your function. But this is an hidden implementation detail. In spirit, each call gets a new (n) for_yan And it does not return 0, because by the time you get into this method
with argument zero, you already summed up all prevuuous guys and it retutns the last one as zero
and you sum it to waht you alredy have, the total result will not be zero.
It will be zero only if zero step is very fisrt one in your summation
and then you'll get that f(0)=0, which will be correct. mrjoltcola >>@for_yan: because by the time you get into this method with argument zero, you already summed up all prevuuous guys and it retutns the last one as zero

Actually this is incorrect. The way recursion works is that the evaluation (summing up all previous guys) doesn't happen in theory, until the last call returns. Then as the stack unwinds, the summation happens.

return n + mystery(n-1);    <-- The "n +" part doesnt happen until the very final "return 0" happens.

return 0;   // at this point, we have n of 3, 2, 1 all stored on the stack. As the last one returns, all the adds are executed

(Though tail recursion can optimize this away) for_yan I agree, I used incorrect wording mrjoltcola Hey, CrazyOne, you are a car nut, and you know carburetors and turbos. mrjoltcola >>I agree, I used incorrect wording

Well, if the compiler does tail-call optimization, you would be correct. But that is an implementation detail that I wanted to be clear, not to confuse the asker. for_yan Yes, but you are right, it is easier to understand, if we say that we have them all prepared for summation, so that even the last one is zero, but the total becomes something - to address this piece of the asker's question CrazyOne Ok cool so in a sense when the recursion gets to 0 am I correct in assuming at this point it checks to see if the stack is empty and if it is not then it pops each element one at a time and in this case adds each of those element together, and returns the summed value to the caller? for_yan What you are saying seems to make sense to me, let's wait waht mrjoltcola says - he obviously understands this stuff much better. mrjoltcola  THIS SOLUTION IS ONLY AVAILABLE TO MEMBERS.
View this solution by signing up for a free trial.
Members can start a 7-Day free trial and enjoy unlimited access to the platform. CrazyOne Referring to your comment ID 35756191 in which I am gathering it is the unwinding where it all comes together. So in this case the actual function would be O(2n) if there were such a thing as O(2n). In other words the function cycles through twice. If this is correct would it not be more efficient, not programmatically but functionally to do something like the following? Wouldn’t that be a true O(n).

BTW thanks for the info so far it has been quite helpful.
``````intintCount=n;
if(intCount==0)
return0;
else
{
while(n!=0)
{
intCount=intCount+n-1;
n--;
}
}
return intCount;
`````` mrjoltcola The order of an algorithm using recursion depends on the algorithm and how you use recursion. No rule says you only call your function once within each call. For example a binary sort may use recursion to iteratively split an array into smaller and smaller pieces, with more calls the deeper you go.

And in your case, no it does not make 2 cycles per function. Each function call executes once per N, so it would be O(n) already. for_yan So the advnatge of recursion is not in its performance but in simplicity
of programming; some opertaions - liket traversing the file system, is probably very difficult to
prioogram without recursion.

That's what you read in http://en.wikipedia.org/wiki/Recursion_%28computer_science%29 :

In languages (such as C and Java) that favor iterative looping constructs, there is usually significant time and space cost associated with recursive programs, due to the overhead required to manage the stack and the relative slowness of function calls; in functional languages, a function call (particularly a tail call) is typically a very fast operation, and the difference is usually less noticeable.

As a concrete example, the difference in performance between recursive and iterative implementations of the "factorial" example above depends highly on the language used. In languages where looping constructs are preferred, the iterative version may be as much as several orders of magnitude faster than the recursive one. In functional languages, the overall time difference of the two implementations may be negligible; in fact, the cost of multiplying the larger numbers first rather than the smaller numbers (which the iterative version given here happens to do) may overwhelm any time saved by choosing iteration. CrazyOne I kind of understand what you are saying it is just hard for me to vision in this case that this particular function isn’t a loop. I mean it is acting like a loop in that it is calling on itself several times to complete its action just like a loop does at least that is the way I am seeing it.  :-) mrjoltcola A loop uses the same variables, in the same scope.

Recursion uses a new set of variables in a new scope. webdev2000 Java

Java is a platform-independent, object-oriented programming language and run-time environment, designed to have as few implementation dependencies as possible such that developers can write one set of code across all platforms using libraries. Most devices will not run Java natively, and require a run-time component to be installed in order to execute a Java program.

102K
Questions
--
Followers
--
Top Experts
Get a personalized solution from industry experts

TRUSTED BY           