Recursion that returns a value

A recursive function can return a value, and that's where recursion gets useful. The classic example is the factorial. The factorial of 5, written 5!, is 5 * 4 * 3 * 2 * 1 = 120. Look closer and 5! is 5 * 4!, and 4! is 4 * 3!, and so on down to 1!, which is 1 (and 0! is 1 too). A definition that uses a smaller version of itself is exactly what a recursive function needs:

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


for i in range(1, 6):
    print(f"{i}! = {factorial(i)}")

1! = 1
2! = 2
3! = 6
4! = 24
5! = 120

factorial(4) can't finish before it knows factorial(3), which waits for factorial(2), which waits for factorial(1). That one is the base case and returns 1 right away. Then the answers travel back the way they came:

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

Watching the calls

A print when a call starts and another before it returns show the order of events. This function adds up the digits of a number: the last digit is n % 10, and the number without it is n // 10. A number below 10 is a single digit, the base case:

def digit_sum(n):
    print("start", n)
    if n < 10:
        result = n
    else:
        result = n % 10 + digit_sum(n // 10)
    print("return", result, "for", n)
    return result


print(digit_sum(472))

start 472
start 47
start 4
return 4 for 4
return 11 for 47
return 13 for 472
13

The call for 472 started first and finished last. Python keeps the unfinished calls waiting on the call stack, the newest on top. When the call on top returns, the one below it carries on from where it stopped, with the value it was waiting for.

The missing return

A common mistake is to work out the result of the recursive call but forget to return it. A function that ends without return returns None, and the call waiting for an answer gets None:

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


print(factorial(3))

Traceback (most recent call last):
  File "main.py", line 7, in <module>
    print(factorial(3))
          ~~~~~~~~~^^^
  File "main.py", line 4, in factorial
    n * factorial(n - 1)
    ~~^~~~~~~~~~~~~~~~~~
TypeError: unsupported operand type(s) for *: 'int' and 'NoneType'

factorial(2) worked out 2 * 1 but threw the result away and returned None, so factorial(3) tried to calculate 3 * None. The fix is return n * factorial(n - 1).