Comparing recursion and loops using two scripts (basic factorial)

[Drone4four]

The “factorial” of the integer 5 is the product of the first 5 integers multiplied against each other. So, 1*2*3*4*5 = 120.

Here is a script modelling the factorial of 5 using a for loop:

def fact(num):
   factorial = 1
   for i in range(1, num + 1):
       factorial = factorial * i
   return factorial
 
 
if __name__ == "__main__":
   fact(5)

For every iteration through the loop at lines 3 and 4, the factorial variable is redefined, where it is multiplied against itself by the iterator, i. So factorial on the first iteration goes from 1 to 1, and is then modified to become 2, which becomes 6, then 24, then 120. Once the range is exhausted, the script returns the product, which is the end result. That makes sense I think.

Here is a factorial script which uses recursion:

def factorial_recursive(n):
   # Base case: 1! = 1
   if n == 1:
       return 1
   # Recursive case: n! = n * (n-1)!
   else:
       return n * factorial_recursive(n-1)
  
  
if __name__ == "__main__":
   factorial_recursive(5)

I believe this recursive model for factorial multiplies backwards from the highest number to the least. For example, 5*4*3*2*1 = end product. Once it reaches 1, I’d expect that this function to return 1. When I follow along in my debugger, n slowly does count down from 5 to 1 (as I expect) however what baffles and perplexes me now is how or why the function returns 120 because as n descends from 5, n just decrements until it reaches 1 and then returns True (1) when the conditional verifies that n == 1. So no matter how large the initial parameter, I’d expect this script just to keep counting down to 1. So the output, regardless of the integer value passed in, should always be the same: 1 (or True). So this recursive algorithm is less of a factorial calculator and more just useless scripts which counts backward from n. Yet miraculously it actually returns the correct factorial. Could someone clarify what is going on here in this recursive script?

According to programiz, when passing in 3 as the argument (instead of 5), here is another interpretation of what is going on in the recursive script:

factorial(3)          # 1st call with 3
3 * factorial(2)      # 2nd call with 2
3 * 2 * factorial(1)  # 3rd call with 1
3 * 2 * 1             # return from 3rd call as number=1
3 * 2                 # return from 2nd call
6                     # return from 1st call

What I think is throwing me off is that my debugger in VSC for the original for loop implementation (above) tosses three variables around at code execution: factorial, i, and num. With each iteration, my debugger shows each variable increment, which is enormously helpful to observe how factorials work in general. But when executing the recursive script, my debugger only shows n decrement at each pass which makes it more difficult to observe the recursive operation.

As Wikipedia explains, there are many advanced topics involving factorials and number theory which is way beyond my 8th grade-level proficiency in math.

For what it is worth, here is my valiant (but failed) attempt at converting the original for loop into list comprehension:

def fact(num):
    factorial = 1
    return [factorial * i for i in range(1, num + 1)]

if __name__ == "__main__":
    fact(5)

If someone would kindly correct my list comprehension attempt in this context, that I think might help too.

[deanhystad]

Now you unwind the recursion.  You still have your first call factorial(5) waiting for the result of calling factorial(4) which is waiting for factorial(3) which is waiting for factorial(2) which has finally gotten a result for calling factorial(1).  So now factorial(2) uses the result of factorial(1) and returns 2x1.  Now that factorial(2) is done, factorial(3) can run and multiply the result of factorial(2) times 3.  factorial(3) returns 1x2x3 allowing factorial(4) to run which returns 1x2x3x4 to factorial(5).  And finally factorial(5) can return the result of factorial(4)x5 so you get 1x2x3x4x5 = 120.

def recursive_factorial(n):
    if n < 3:
        return n
    return n*recursive_factorial(n-1)

def non_recursive_factorial(n):
    a = 1
    for b in range(2, n+1):
        a *= b
    return a

## Anyone needing a factorial
import math

print(recursive_factorial(5), non_recursive_factorial(5), math.factorial(5))

[ndc85430]

If it helps, the book Grokking Algorithms has lots of nice diagrams, including ones for recursion showing the stack of function calls that go on in the recursive calls.

[deanhystad]

There is a special place reserved in hell for people who write this kind of code:

def factorial(n):
    return [(f := f * i) if i > 0 else (f := 1) for i in range(n+1)]

## This looks so much nicer
def factorial(n):
    f = 1
    for i in range(1, n+1):
        f = f * i
        yield f