understanding basic recursion

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.


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.


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.