Thinking Recursively

A function that calls itself

Recursion means solving a problem by solving a smaller version of the same problem. In code, it's a function that calls itself.

Think of it like this: You're in a long queue and want to know your position. You ask the person in front: “what's your position?”. They ask the person in front of them... The first person says “1” (the base case). Then each person adds 1 to the answer they got and passes it back.

def countdown(n):
    if n == 0:                 # base case: stop here
        print("Lift off!")
        return
    print(n)
    countdown(n - 1)           # smaller problem

countdown(3)

Output

3
2
1
Lift off!

The two rules

• Base case – the smallest problem, answered directly without recursion.
• Recursive step – make the problem smaller and call the function again. Every call must get closer to the base case.

Returning answers

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

print(factorial(5))

Output

120

The call stack

Each call waits for the one it made to finish. Python keeps the waiting calls on the call stack:

def factorial(n, depth=0):
    print("  " * depth + f"factorial({n}) called")
    if n <= 1:
        result = 1
    else:
        result = n * factorial(n - 1, depth + 1)
    print("  " * depth + f"factorial({n}) returns {result}")
    return result

factorial(3)

Output

factorial(3) called
  factorial(2) called
    factorial(1) called
    factorial(1) returns 1
  factorial(2) returns 2
factorial(3) returns 6

Common mistake: No base case (or a step that never reaches it) means the function calls itself forever, until Python stops it with a RecursionError.