Python Recursion

A recursive function calls itself on a smaller input. Every recursion needs a base case that stops the calls, and every recursive step must move toward that base case. When those two conditions hold, recursion can make a nested problem much shorter to express. You will also trace the call stack, flatten nested lists, and memoize repeated branches.

Start with a base case

The base case is the smallest input you can answer without another call. factorial(1) returns 1 immediately. Without a base case, the function keeps calling itself until Python raises a RecursionError.

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

print(factorial(5))

One recursive call

Two calls, smaller inputs

Fibonacci is a natural two-branch recursion: fib(n) depends on fib(n - 1) and fib(n - 2). The first two values are the base cases. Draw the call tree for a small n to see why this version repeats work.

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(6))

A branching recursion

Walk a nested list

A recursive list function handles the first item, then delegates the rest to a smaller list. The empty list is the base case. This pattern is useful for trees and nested structures, not just flat lists.

def total(items):
    if not items:
        return 0
    return items[0] + total(items[1:])

print(total([1, 2, 3]))

Shrinking the list

The stack unwinds in reverse

Each recursive call pauses its caller. The base case returns first, then each caller resumes and combines the returned value. Printing on the way down and on the way up makes the order visible and explains why the final result is built from the inside out.

def walk(n):
    if n == 0:
        print("base")
        return 0
    print("enter", n)
    result = walk(n - 1) + n
    print("leave", n, "result", result)
    return result

print("total", walk(3))

Enter downward, combine upward

Return a new structure, not a global

A recursive function should return its partial result. A global accumulator makes repeated calls interfere and is hard to test. Flatten nested lists by combining the result for the first item with the result for the rest.

def flatten(items):
    if not items:
        return []
    first, *rest = items
    if isinstance(first, list):
        return flatten(first) + flatten(rest)
    return [first] + flatten(rest)

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

Combine returned values, not shared state

Memoize repeated branches

Naive Fibonacci repeats the same subproblems. lru_cache stores results by argument and turns exponential work into linear work for this shape. Memoization is only safe when the function is pure and its arguments are hashable.

from functools import lru_cache

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

print(fib(30))
print(fib.cache_info().hits > 0)

Cache pure subproblems

Try it yourself

Change the values, predict the output, then run the code. The Python runtime is downloaded the first time you press Run, so the first run can take a few seconds.