Recursion: How It Works

The idea

def countdown(n):
    if n == 0:              # base case: stop here
        print("liftoff")
        return
    print(n)
    countdown(n - 1)        # recursive case: a smaller problem


countdown(3)

3
2
1
liftoff

Every recursive function has exactly two parts:

• A base case that returns without recursing.
• A recursive case that calls itself with an input closer to the base case.

Miss the base case, or fail to make progress towards it, and the function recurses until Python stops it.

Following the calls

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


print(factorial(5))       # 120

factorial(5)
= 5 * factorial(4)
= 5 * (4 * factorial(3))
= 5 * (4 * (3 * factorial(2)))
= 5 * (4 * (3 * (2 * factorial(1))))
= 5 * (4 * (3 * (2 * 1)))            <- base case reached
= 5 * (4 * (3 * 2))
= 5 * (4 * 6)
= 5 * 24
= 120

Note that nothing is multiplied on the way down. The calls stack up until the base case, and the multiplications happen on the way back out.

The call stack

def trace(n, depth=0):
    print("  " * depth + f"enter trace({n})")
    if n == 0:
        print("  " * depth + "base case")
    else:
        trace(n - 1, depth + 1)
    print("  " * depth + f"leave trace({n})")


trace(3)

enter trace(3)
  enter trace(2)
    enter trace(1)
      enter trace(0)
      base case
      leave trace(0)
    leave trace(1)
  leave trace(2)
leave trace(3)

Each call gets its own frame on the call stack, holding its own parameters and local variables. Nothing is shared between them unless you pass it explicitly.

The recursion limit

import sys

print(sys.getrecursionlimit())        # 1000 by default


def forever(n):
    return forever(n + 1)


# forever(1)     # RecursionError: maximum recursion depth exceeded

Python caps recursion depth at about 1000 frames, deliberately, so that runaway recursion raises a clean error instead of crashing the interpreter. Raising the limit with sys.setrecursionlimit is possible and is almost never the right answer; if you need thousands of levels, rewrite the function as a loop.

Python does not perform tail call optimisation. A recursive call at the end of a function still consumes a stack frame, unlike in some other languages. This is a deliberate design decision, kept so that tracebacks remain complete and readable.

Recursion and iteration side by side

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


def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result


print(factorial_recursive(10), factorial_iterative(10))

In Python, prefer iteration for anything that is naturally a sequence. Prefer recursion when the data is recursive: a directory inside a directory, a dictionary inside a dictionary, a tree, or a problem that splits cleanly in half.

Classic examples

Sum of a list

def total(numbers):
    if not numbers:                 # base case: empty list
        return 0
    return numbers[0] + total(numbers[1:])


print(total([1, 2, 3, 4]))          # 10

Correct, and quietly expensive: numbers[1:] copies the rest of the list on every call. This is a teaching example, not production code.

Reversing a string

def reverse(text):
    if len(text) <= 1:
        return text
    return reverse(text[1:]) + text[0]


print(reverse("python"))            # nohtyp

Palindrome check

def is_palindrome(text):
    if len(text) <= 1:
        return True
    if text[0] != text[-1]:
        return False
    return is_palindrome(text[1:-1])


print(is_palindrome("racecar"), is_palindrome("python"))    # True False

Greatest common divisor

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


print(gcd(48, 18))                  # 6

This one is genuinely better as recursion: the mathematical definition is recursive, and it converges in very few steps.

Binary search

def binary_search(items, target, low=0, high=None):
    if high is None:
        high = len(items) - 1
    if low > high:
        return -1
    middle = (low + high) // 2
    if items[middle] == target:
        return middle
    if items[middle] < target:
        return binary_search(items, target, middle + 1, high)
    return binary_search(items, target, low, middle - 1)


values = [1, 3, 5, 7, 9, 11]
print(binary_search(values, 7))     # 3
print(binary_search(values, 4))     # -1

Where recursion is clearly right

def flatten(items):
    result = []
    for item in items:
        if isinstance(item, list):
            result.extend(flatten(item))
        else:
            result.append(item)
    return result


print(flatten([1, [2, [3, [4, [5]]]], 6]))       # [1, 2, 3, 4, 5, 6]

def count_leaves(data):
    if isinstance(data, dict):
        return sum(count_leaves(v) for v in data.values())
    if isinstance(data, list):
        return sum(count_leaves(v) for v in data)
    return 1


print(count_leaves({"a": [1, 2], "b": {"c": 3, "d": [4, 5]}}))    # 5

Writing either of these with loops means managing your own stack. The recursive versions match the shape of the data, which is the real test of whether recursion is the right tool.

Common mistakes

• No base case, or a base case that can be stepped over - for example testing n == 0 while decreasing by 2.
• Forgetting to return the recursive call, so the result is lost and None comes back.
• Not making progress: calling f(n) instead of f(n - 1).
• Using recursion for a plain counting loop.
• Slicing inside a recursive call over a large list, turning it quietly quadratic.
• Raising the recursion limit instead of rewriting the function.

Best practices

• Write the base case first, before the recursive case.
• Check that every recursive call moves strictly closer to the base case.
• Pass indexes rather than slices when recursing over a sequence.
• Use recursion for recursive data, and loops for sequences.
• Trace by hand for a small input before trusting the code.

Practice

1. Write a recursive function returning the sum of the digits of an integer.
2. Write a recursive power function, then compare it with ** for large exponents.
3. Convert the recursive factorial into a loop and explain what changed in memory use.
4. Write a recursive function counting the files in a nested dictionary of folders.
5. Take a recursive function with a missing return, predict the output, then run it.

Conclusion

Recursion is a base case plus a step that gets closer to it. Every call costs a stack frame and Python allows about a thousand, so use it where the data is genuinely nested - trees, folders, nested structures - and use a loop everywhere else.