R is considered the predominant language for data scientist and statisticians. Learn how to use R for your own data science projects.
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.
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;*/
}
Do more with
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
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.
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.
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)
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)
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.
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.
>>@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)
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)
Hey, CrazyOne, you are a car nut, and you know carburetors and turbos.
Recursion is like if your exhaust fed into your intake. The air is your data, the engine is your code. :)
Recursion is like if your exhaust fed into your intake. The air is your data, the engine is your code. :)
>>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.
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.
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
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?
What you are saying seems to make sense to me, let's wait waht mrjoltcola says - he obviously understands this stuff much better.
At each call of the function, the caller of the function is suspended, waiting on the result. So it just so happens in recursion, the caller and the callee are the same code, but with different context (stack, etc.)
So when, finally, one of the calls returns, that is the tail, and then each "parent" caller resumes as we back out, using the result of the child call to complete the suspended parent calculation, then returning to its own parent, all in succession.
The stack is just where each caller stores the parameters as it calls the next one, and where it stores its local variables, if any.
func(n) =>
n + func(n - 1)
So that is really:
func(3) =>
3 + func(2) =>
2 + func(1) =>
1 + func(0) =>
return 0
Does that help? If not feel free to keep asking.
So when, finally, one of the calls returns, that is the tail, and then each "parent" caller resumes as we back out, using the result of the child call to complete the suspended parent calculation, then returning to its own parent, all in succession.
The stack is just where each caller stores the parameters as it calls the next one, and where it stores its local variables, if any.
func(n) =>
n + func(n - 1)
So that is really:
func(3) =>
3 + func(2) =>
2 + func(1) =>
1 + func(0) =>
return 0
Does that help? If not feel free to keep asking.
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.
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;
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.
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.
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.
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.
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. :-)
A loop uses the same variables, in the same scope.
Recursion uses a new set of variables in a new scope.
Recursion uses a new set of variables in a new scope.
This is a nice simple example of using recursion with Java.
http://learn-java-by-example.com/2010/java/fibonnaci-number
http://learn-java-by-example.com/2010/java/fibonnaci-number
Premium Content
You need an Expert Office subscription to comment.Start Free Trial