Lesson 5 of 9

Recursion

A recursive calls itself on a smaller piece of the problem until the piece is small enough to answer directly. The next two lessons, on trees and sorting, rely on it.

Every recursive function has two parts: a base case — the input so small the answer is immediate — and a recursive case that shrinks the problem and calls itself. Miss the base case, or fail to shrink, and calls nest forever until the overflows. The mental model: trust the recursive call. Assume it correctly solves the smaller problem, and only ask 'how do I combine that answer into mine?'


def factorial(n):
    if n <= 1:                    # base case: answer is immediate
        return 1
    return n * factorial(n - 1)   # shrink, recurse, combine

factorial(5)     # 5 * 4 * 3 * 2 * 1 = 120

# What the call stack does:
# factorial(5)
#   factorial(4)
#     factorial(3)
#       factorial(2)
#         factorial(1) -> 1      base case hit, stack unwinds
#       -> 2 * 1 = 2
#     -> 3 * 2 = 6
#   -> 4 * 6 = 24
# -> 5 * 24 = 120

shines on nested data, where get awkward: a folder contains files and folders, which contain files and folders. The structure is recursive, so the cleanest code is too. Anything a loop does, recursion can do and vice versa — but for -similar structures, recursion mirrors the shape of the data.


import os

def total_size(path):
    if os.path.isfile(path):                  # base case: a file
        return os.path.getsize(path)
    total = 0
    for name in os.listdir(path):             # recursive case: a folder
        total += total_size(os.path.join(path, name))
    return total


from functools import lru_cache

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

fib(50)    # instant — each fib(k) computed once, then cached

Finished reading?Mark it done to track your progress.

Tip: use the ← and → keys to move between lessons.