Recursion in Python

Here is an idea that sounds strange at first: a function is allowed to call itself. This is called recursion in Python, and it is one of the most elegant ideas in all of programming — used for anything that naturally breaks into smaller versions of itself, like tree structures and mathematical sequences.

What you will learn

• How a function calling itself actually works, step by step
• The base case — what stops recursion from running forever
• How to trace the classic factorial() and fibonacci() examples
• The leap of faith — the right way to think about recursive calls
• Guarding a recursive function against bad input
• What happens when you forget the base case: RecursionError

A first example: counting down

def countdown(n):
    if n <= 0:
        print('Blastoff!')
    else:
        print(n)
        countdown(n - 1)

Call it with countdown(3) and here is what happens, step by step:

• countdown(3) — is 3 ≤ 0? No. Prints 3, then calls countdown(2).
• countdown(2) — is 2 ≤ 0? No. Prints 2, then calls countdown(1).
• countdown(1) — is 1 ≤ 0? No. Prints 1, then calls countdown(0).
• countdown(0) — is 0 ≤ 0? Yes! Prints 'Blastoff!' and stops.

# Output:
3
2
1
Blastoff!

Each call to countdown creates a smaller version of the same problem. The function keeps going until it reaches the stopping condition — called the base case. The base case is what prevents the function from calling itself forever.

Stack diagrams for recursive functions

Each time a function is called, Python creates a frame — a little box holding that function's local variables. Recursion creates a more dramatic version of this: every time a function calls itself, Python creates a brand new frame on the stack, completely separate from the others.

For countdown(3), the stack looks like this at its deepest point, just before countdown(0) prints "Blastoff!":

__main__
countdown   n = 3
countdown   n = 2
countdown   n = 1
countdown   n = 0   <- base case

Each frame is completely independent — the n inside countdown(3) has no connection to the n inside countdown(2); they are separate boxes, just with the same label inside them. When the base case runs and returns, the frames start collapsing from the bottom upward: countdown(0) finishes and disappears, countdown(1) picks up where it left off, then countdown(2), then countdown(3), until control returns to __main__. This collapsing is why recursive functions actually finish.

The factorial function: recursion that returns a value

Factorial has a mathematical definition that refers to itself: 0! = 1, and n! = n × (n-1)!. So 3! = 3 × 2! = 3 × 2 × 1! = 3 × 2 × 1 × 0! = 3 × 2 × 1 × 1 = 6. This maps almost directly into Python:

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

Trace through factorial(3): it needs factorial(2), which needs factorial(1), which needs factorial(0), which returns 1 (the base case). Then the results flow back up: 1 × 1 = 1, then 2 × 1 = 2, then 3 × 2 = 6.

The leap of faith: trusting your own functions

Tracing through recursive calls in your head gets overwhelming fast. There is a better way to think about it — the leap of faith.

When you call math.sqrt(), you do not dig into its source code to verify it works — you just trust it. Apply the same thinking to your own functions. When you write factorial(n) and it calls factorial(n-1), do not follow the chain — just ask: if I assume factorial(n-1) gives the correct answer, can I compute factorial(n) from it? If yes — multiply by n — then your logic is correct. Trust the function to handle the rest. This is not laziness; it is the right mental model for recursive code. Trying to trace every call is what makes your head explode.

Fibonacci: recursion with two calls

The Fibonacci sequence is defined as fibonacci(0) = 0, fibonacci(1) = 1, and fibonacci(n) = fibonacci(n-1) + fibonacci(n-2):

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

This function makes two recursive calls, so the call tree branches instead of forming a straight chain. Trying to trace it manually for even moderate values of n is impractical — the leap of faith is especially important here: assume both recursive calls return correct results, and the logic becomes obvious: add them together.

Guarding against bad input

What happens if you call factorial(1.5)?

factorial(1.5)   # RecursionError: maximum recursion depth exceeded

The base case checks for n == 0, but 1.5 never hits zero — it goes 0.5, -0.5, -1.5... forever. The fix is to guard against bad input at the start of the function using isinstance():

def factorial(n):
    if not isinstance(n, int):
        print('Factorial is only defined for integers.')
        return None
    elif n < 0:
        print('Factorial is not defined for negative integers.')
        return None
    elif n == 0:
        return 1
    else:
        return n * factorial(n - 1)

factorial('fred')   # Factorial is only defined for integers.
factorial(-2)        # Factorial is not defined for negative integers.
factorial(5)         # 120

The first two conditions are called guardians — they intercept invalid inputs before the real logic runs. Guardians are a clean pattern for making functions robust without complicating the core logic.

Infinite recursion: what happens when you forget the base case

If a recursive function never reaches its base case, it calls itself forever — or rather, it tries to. Python has a built-in safety limit of 1000 recursive calls; after that, it stops the program and throws an error:

def recurse():
    recurse()    # no base case — will call itself forever

# RecursionError: maximum recursion depth exceeded

The error message Python gives you has a traceback hundreds of lines long, all showing the same function calling itself over and over. If you ever see this, the fix is always the same: find your base case, make sure it is there, and make sure every recursive call is actually moving toward it.

Common mistakes

• Forgetting the base case entirely, causing a RecursionError
• Writing a base case that the recursive calls never actually reach (like checking for exactly 0 when the input can be a float)
• Trying to trace every single call in your head instead of trusting the leap of faith
• Using recursion for simple repetition where a for loop would be clearer
• Forgetting to guard against invalid input types before recursing