Algorithms · Lesson 3 of 6

Recursion

Base cases, recursive cases, the call stack and when to avoid recursion.

• Intermediate
• 15 min read
• 3 objectives

Before this lessonLesson 2: Sorting

A recursive function solves a problem by calling itself on a smaller version of the same problem. It feels odd at first, but many problems (trees, nested folders, divide-and-conquer) are naturally recursive, and the code ends up shorter than a loop.

Solving a problem by shrinking it

Recursion means a function that calls itself on a smaller version of the same problem. Russian nesting dolls are a good picture: to count the dolls, open the outer one, count what is inside, add one. Every recursive solution needs two parts: a base case (the smallest problem, answered directly) and a recursive case (reduce the problem and trust the function to solve the smaller one). Forget the base case and the function never stops.

Two required parts

• Base case: the smallest problem, answered directly. Without it, the function never stops.
• Recursive case: reduce the problem and call yourself, trusting that the call returns the right answer for the smaller input.

def factorial(n):
    if n <= 1:               # base case
        return 1
    return n * factorial(n - 1)   # recursive case

print(factorial(5))

120

The call stack

Each call waits for the one it started. factorial(3) becomes 3 * factorial(2), which becomes 3 * (2 * factorial(1)); when the base case returns 1, the stack unwinds multiplying as it goes. Each waiting call uses memory, so Python limits depth (about 1000) and raises RecursionError if you exceed it.

More examples

def sum_list(a):
    return 0 if not a else a[0] + sum_list(a[1:])

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

def power(x, n):                    # fast exponent, O(log n)
    if n == 0:
        return 1
    half = power(x, n // 2)
    return half * half * (x if n % 2 else 1)

print(sum_list([1, 2, 3]), reverse("abc"), power(2, 10))

6 cba 1024

Recursion on nested data

Recursion shines when data has no fixed depth, like a nested list or a directory tree.

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

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

[1, 2, 3, 4, 5]

The Fibonacci trap

Naive fib(n) = fib(n-1) + fib(n-2) recomputes the same values over and over and takes exponential time. Caching results fixes it, which leads straight into dynamic programming.

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

print(fib(50))

12586269025

Recursion vs iteration

Anything recursive can be written with a loop and an explicit stack. Prefer a loop when depth could be large or the loop is just as clear; prefer recursion when it mirrors the structure of the problem.

Factorial, traced

def factorial(n):
    if n <= 1:                  # base case
        return 1
    return n * factorial(n - 1) # recursive case

print(factorial(5))

120

Trace it: factorial(3) waits for factorial(2), which waits for factorial(1). That returns 1, then 2 * 1 = 2, then 3 * 2 = 6. Each call waits on the call stack until the one below finishes.

Watch the calls happen

def countdown(n, depth=0):
    print("  " * depth + f"countdown({n})")
    if n == 0:
        print("  " * depth + "liftoff")
        return
    countdown(n - 1, depth + 1)
    print("  " * depth + f"back in countdown({n})")

countdown(2)

countdown(2)
  countdown(1)
    countdown(0)
    liftoff
  back in countdown(1)
back in countdown(2)

Worked example: summing a nested list

def total(node):
    if isinstance(node, int):
        return node
    return sum(total(child) for child in node)

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

21

Making Fibonacci fast with memoization

The obvious version recomputes the same values over and over, taking exponential time. Remembering answers (memoization) turns it linear.

from functools import lru_cache

calls = 0

def slow(n):
    global calls
    calls += 1
    return n if n < 2 else slow(n - 1) + slow(n - 2)

@lru_cache(None)
def fast(n):
    return n if n < 2 else fast(n - 1) + fast(n - 2)

print(slow(20), "calls:", calls)
print(fast(20), "cache size:", fast.cache_info().currsize)

6765 calls: 21891
6765 cache size: 21

Key takeaways

• Every recursive function needs a base case and a step that moves toward it.
• Calls stack up and unwind; a missing base case causes a stack overflow.
• Recursion suits nested and tree-shaped data; memoize when subproblems repeat.

# Write your solution here