Understanding factorial recursion [duplicate]

Question

This question already has answers here:

Understanding recursion in Python (4 answers)

Closed 3 years ago.

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.

Answer 2

This may be helpful

(factorial 4)
(4 * (factorial 3))
(4 * (3 * (factorial 3)))
(4 * (3 * (2 * (factorial 1))))
(4 * (3 * (2 * 1)))
(4 * (3 * 2))
(4 * 6)
(24)

Answer 3

Yes, the way you've described it is what is going on.

One point to note with your code, if you enter a non-integer value for n or a value of n less than 0, it looks like you will be stuck in an infinite loop.

It might be worth adding a check in your code for this:

if not isinstance(n, int): 
      return None

 elif n < 0: 
      return None