Understanding factorial recursion [duplicate]

Question

I'm looking over the factorial example of recursion and would just like to make sure that I'm understanding it correctly!

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

Would I be right in saying:

factorial(4) = factorial(4-1) * 4 = factorial(3-1) *3 *4 = factorial(2-1) *2 *3 *4 = factorial(1-1) *1 *2 *3 *4 = 24

because factorial(1-1) = factorial(0) which as the base case shows = 1 and then we multiply by 2, then 3 then 4.

Is that the correct way of looking at it?

Thanks in advance!

Answer 1

Yes it is. But since it's recursion, it works the opposite way. I once had an interviewer explain it to me like this :

Say, for fact(5) :

 - fact(5) = 5 * fact(4)
           - fact(4) = 4 * fact(3)
                     - fact(3) = 3 * fact(2)   
                               - fact(2) = 2 * fact(1)
                                         - fact(1) = 1 * fact(0) 
                                                   - fact(0) = 1
                                                   // This is where your condition returns 1.

Now, imagine that the - sign above stands for a return. You basically return whatever is after the - sign. So from the lowest line, 1 is returned. Then, you have 1 returned in fact(1) i.e. 1 * 1. So it happens in a REVERSE cascade like :

 = 120
 - fact(5) = 5 * 24
           - fact(4) = 4 * 6 = 24
                     - fact(3) = 3 * 2 = 6  
                               - fact(2) = 2 * 1 = 2
                                         - fact(1) = 1 * 1 = 1
                                                   - fact(0) = 1

Remember that whenever you work on recursion, everything actually works in reverse. That should really help you breaking any recursion problem down.

This is actually why tail recursion and the related optimization are so important. In memory, each of those calls is delayed and can't return until the calls above it (below in the diagram) finish and return. So a very deep recursive call can cause a stack overflow unless the compiler/interpreter optimize this by turning it into the version in the OP, such that the partial results are evaluated immediately and not delayed. Python does not perform this optimization and so you must be careful with your recursive calls.