understanding basic recursion

Question

public static void main (String[] args)
{
    System.out.println(factorial(5));
}

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

I wrote the above directly in here so may not compile but think it does.

Can anyone breiefly explain how this works in the sence that how is it stored? It starts off by calculating 5 * (5-1), then down to 4 * (4-1) then 3 * (3-1)..... until it gets to 1 which will just return 1 right? sorry for being so sketchy i would just be interested to find out how this works exactly

thanks

but as it works it out - it gets the values for the individual stages

5*(5-1) 4 * (4-1) ... ... ...

how are these stored and then retrieved back or am i missing something?

Answer 1

....then 3 * (3-1)..... until it gets to 1 which will just return 1 right?

right, but it returns that '1' to the next-to-last invocation, which will multiply by two, returning '2'... to the next-to-next-to-last, which will multiply by three.....

Answer 2

Yes you have it right in the code, it first checks the value of n if it is less than or equal to 1, that is what is referred to as your base case. They are important, they tell your recursive function when to stop.

If the value of n is not less than or equal, it returns the value of n multiplied by the recursive call of factorial but with the value n-1 up until it reaches it's base case: if (n <= 1) where it returns 1

Your base case was set up by the factorial definiton of 0! and 1! which are both equal to 1.

Maybe this diagram might help to understand how the calls work.

5 * fact(5-1) ->
          4 * fact(4-1) ->
                    3 * fact(3-1) ->
                              2 * fact(1) 
                                       1

Which is the same as 5! or 5 x 4 x 3 x 2 x 1

Hope this helps.

Answer 3

Imagine you are the computer, and someone hands you a paper with

factorial(3)

written on it. You then execute the procedure, looking at the argument. Since it's > 1, you write

factorial(2)

on another piece of paper and "hand it to yourself", waiting until you get the answer to that one before proceeding.

Again you execute the procedure. Since 2 is still > 1 you write

factorial(1)

on yet another piece of paper and hand it to yourself, waiting until you get the answer to this one before proceeding.

Again, you execute the procedure. This time the input is 1, so you take the first branch and return 1. The invocation that was processing factorial(2) now has an answer so it multiplies 2 by that answer (1) and returns. Now the invocation that was handling factorial(3) gets its answer (2) and multiplies it by 3, giving 6. It then returns that answer to the person who started the whole operation.

If you imagine that you kept the pieces of paper in a stack in front of you as you were working, that is a visualization of the "stack" in the computer's memory. Each recursive invocation stores the parameter (and any temporary variables) on its own piece of paper (stack frame) literally arranged as a pushdown stack just like the papers, one on top of the other.

Answer 4

Are you asking how recursion works internally? The one sentence answer is that every thread has a "call stack" and every time a method is called, a new entry gets pushed onto this stack, which has information about which method is called, and what the arguments were. When the method is finished it places its return value back on the same stack and the calling method pulls it off. So at its height your stack will look like

factorial (1) called by factorial (2) called by factorial (3) called by factorial (4) called by factorial (5)

The Wikipedia article on call stacks seems pretty thorough at first glance.

Answer 5

1. In the initial call to factorial, n=5, and is pushed on the stack.
2. Then the else is triggered so 4 is passed to factorial, and is also pushed onto the stack.
3. Then the else is triggered so 3 is passed to factorial, and is also pushed onto the stack.
4. Then the else is triggered so 2 is passed to factorial, and is also pushed onto the stack.
5. Then the else is triggered so 1 is passed to factorial, and is also pushed onto the stack.
6. Then the else is triggered so 0 is passed to factorial, and is also pushed onto the stack.
7. The if gets triggered and 1 is returned to the calling factorial.
8. The if gets triggered and 2 * 1 is returned to the calling factorial.
9. The if gets triggered and 3 * 2 is returned to the calling factorial.
10. The if gets triggered and 4 * 3 is returned to the calling factorial.
11. The if gets triggered and 5 * 4 is returned to the calling factorial.

The stack also gets cleaned up, however that gets too tedious to type. Essentially all values in a method call are pushed onto the stack, and popped off the stack on the methods return. This keeps them separated between recursive calls.

Answer 6

Its important to note that "recursion" works differently in java (a procedural language) than it does in say Haskell or F# (functional languages).

In Java when we invoke recursion we do so by evaluating the expression tree and resolving each part of it until we determine the value of each part of the expression. If we need to invoke another function we put in a place holder for all intermediate values at that point and then begin to build a new expression tree for the new function.

In the case of recursion what we are doing is making a call to the same function, hopefully with different terminating values, which needs to be resolved before we can complete the evaluation of the current expression. These expansions are chained together repeatedly until one of two things happens 1) We reach a terminating expression which returns control to the caller (the first part of your if in this case), or we exhaust our ability to place intermediate values in storage and we return an exception (Stack overflow).

In the first case we then begin resolving each of the expression trees from the top of the stack, working our way backwards until their are no stack entries left, at which point the expression tree resolves to the final value returned.

Jim's answer is an excellent physical metaphor for this.

Answer 7

It's hard to guess exactly what part of recursion you're having difficulty with, but I'm going to go off this part of your question:

until it gets to 1 which will just return 1 right?

I'm guessing you mean, "if it will just return 1, why is the result of the function not 1?"

Consider that when you return from a function (in this case, factorial) you are returning a value to whomever originally asked for it.

If I say "give me factorial(5)" then factorial(5) will return me a value, but before it can return me the value it has to ask factorial(4) for its value, factorial(5) essentially says "give me factorial(4) so I can multiply it by 5 and give it back to the guy who asked for factorial(5)." Now factorial(4) will return its value to factorial(5) which can multiply it by n and return its value back to me. Recall, I didn't ask for factorial(4)'s value, I don't even care, and it didn't come back to me, it went back to factorial(5).

By the time you hit factorial(1) you'll have factorial(2), factorial(3), factorial(4) and factorial(5) all waiting to get an answer back. Factorial(1) will be return its value (which is 1, because of your base case) to factorial(2), which can finally return to factorial(3) and so on, at which point the recursion will complete and you'll get the value of factorial(5) back.

Answer 8

A practical approach which requires a good IDE (eclipse, netbeans, IntelliJ):

Add a breakpoint to the line which reads return 1 and debug the application. When it stops, look at the stack trace. You'll see that the factorial method has been called several times.

The eclipse Debug view shows the suspended thread and a stack with six entries, each line representing a line of code where another method is called (except for the top entry - that's the breakpoint). factorial appears five times, you can select each line and see the value of n in the Variable view (this is basic and should work on the other IDE in a similiar way).

That should give another idea how recursive method calls work (and why you receive an out of memory error when you do not define the exit criteria properly ;) )