Recursion?

[Fingerz]

Hi all,

Only been programming a few days now. Got to this section about recursion. Completely confused on how each pass throu the recursive method is being stored until its base case is reached and then calculates from the base case back to 5.

With an argument of 5 being passed f.fact(5)

class factorial{
int fact(int n){
int result;

if(n==1) return 1;
result = fact(n-1)*n;
return result;
}
}

The book only has 2 paragraphs about this subject. Anyone have the patience to helps me understand the inner workings of this would be greatly appreciate. Or some good sites I can use for some better info. TYVM.

[travishein]

internally in the Java VM is what's called a "stack" this is kind of like a stack of plates at a buffet, or the pile of things to do on my desk. where you have a piece of paper with a state and some scribbles on it, (e.g. variable) and then if you were to put another piece of paper over top of that, it has its own space to put variables, possible a varibale name with different values..

so when a function is executed, the current location of the program is stored into the stack, as a "come back to this spot when the function is finished executing."
Within a function, any variables are allocated into the stack (more pices of paper piled up on top of the previous ones), as scratch pads during the scope of the function execution, when the function returns, these are cleaned up.

so recursive functions are a function that calls itself. each invocation of the function has its own 'piece of paper' to store its local variables and function parameter values that it was passed.

in this case, the terminal case is inside the function when it evaluates the parameter passed into it was 1, it simply returns. the program control then returns to the previous function, which its local variables are evaluated, and it returns until all the functions states stored on the stack are back to the main() method and the program exits.

[sunde887]

Check out htdp.org if you want to get a better understanding of how recursion works, the book uses lots of it, and the programming language has a nice visual display of how a program is evaluated so you can see what happens at each step.

[Fingerz]

Ok,
I understood that stacks relied on push and pop, throu arrays. Are those the stacks your refering too? Does Java automatically view recursion and create the stack itself, until the base case is reached? Or amI missing the point?

[ClickerMonkey]

Every time you make a method call you add (push) that 'method' on the stack. Once the method completes it is then removed (popped) off the stack. With recursion you calling method X which is pushed on the stack, in method X it calls method X until some condition - continually pushing more X on the stack... once the condition is met each method is popped off one at a time and finish execution.

I hope this perspective has helped!

[Fingerz]

Ok another question.
Is recursion a built in java class that reconizes that your method is recursive.
So it knows not to process a method until the base case is reached. Once that base case is reached its works its way back up the stack implemented each method on the stack until its base case is reached again. So on and so on until the stack is empty. Only been doing this a few like said earlier so my terminology might be off. Feel free to correct me, actually I would appreciate it :)

[Singing Boyo]

Recursion is when a method calls itself. Java has no need to notice that your method is recursive. It does exactly the same thing with recursive calls as it does with normal method calls. All a program in any language really is is a stack of method calls, and when you end up with the last of the method calls removed from the stack, the program exits. Programs with multiple threads have multiple call stacks - one for each thread, and they only exit, in the case of java, when the stack for all of the threads are empty. (If you don't know what threads are, then don't worry about it.)

[Fingerz]

Ok then what Im confused about is how each value is being return from one method to the next.

with result = fact(n-1) * n
with the argument of f.fact(5) being passed
I see result = (5-1) * 5 given me 20, and not 120 like it sould be.
So what Im not understanding is how the factorial values are being passed back up to the stack. If you could put in terms of how each is being evauluated thats would help a great deal.

[sunde887]

alright, when the function is called it first determines if it's at the base case.

For factorial the base case is 1.
if the base case is not met, it moves on, the second case in factorial would be:

n * factorial(n - 1);

not n * n -1 like you are thinking.

so when it gets the the second case it calls its self with a smaller number.
it continues calling its self until the case of factorial 1 is sent to the stack, when it is, it evaluates to 1 and all the stuff previously on the stack.

so you get n * n - 1 * n - 2 ... * 1.

int factorial(int n)
{
 if(n == 1)
{
   return 1;
 }
 else
{
   return  n * factorial(n - 1);
}
}

for factorial of 5 it works like this

5 == 1? no.
so
5 * factorial(4);
does 4 == 1? no.
4 * factorial(3);
3 * factorial(2);
2 * factorial(1);
1.

once one is met it "cleans up" so to say(probably the wrong term, but it gets my point accross) it goes through the stack and performs the operations.

[Fingerz]

TYVM thats what I was looking for to easy lol. TY you all for your time:)

[sunde887]

Also, if you want a website with some pretty decent recursion problems to play around with and get more familiar, here is a link: CodingBat Java Recursion-1