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

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 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.