Lesson 21 of 34 · 0 of 2 exercises solved

Recursion

A recursive calls itself on a smaller piece of the problem until the piece is trivial. It is the natural way to handle trees, nested data and anything defined in terms of itself.

Every recursive function has two parts: a base case that returns without recursing, and a recursive case that makes progress toward it. Forget the base case and you get RecursionError; forget to make progress and you get the same.

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

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

print(factorial(10), sum_list([1, 2, 3, 4]))

import sys
print(sys.getrecursionlimit())

shines on nested structures because the structure itself is recursive: a directory contains files and directories, a value contains JSON values. The function mirrors the shape of the data.

tree = {
    "name": "house",
    "children": [
        {"name": "downstairs", "children": [{"name": "kitchen", "children": []}, {"name": "living room", "children": []}]},
        {"name": "upstairs", "children": [{"name": "bedroom", "children": []}]},
    ],
}

def show(node, depth=0):
    print("  " * depth + node["name"])
    for child in node["children"]:
        show(child, depth + 1)

def count_nodes(node):
    return 1 + sum(count_nodes(c) for c in node["children"])

show(tree)
print(count_nodes(tree), "rooms")

Divide and conquer splits a problem in half, solves each half recursively and merges. Merge sort is the classic example, and search is the same idea with only one half kept.

def merge_sort(items):
    if len(items) <= 1:
        return items
    mid = len(items) // 2
    left, right = merge_sort(items[:mid]), merge_sort(items[mid:])
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
    return merged + left[i:] + right[j:]

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))

Overlapping subproblems make naive recursion exponential: fib(n) calls fib(n-1) and fib(n-2), which each call fib(n-3)… caches results so each subproblem is solved once. functools.cache does it in one line.

from functools import cache
import time

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

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

t = time.perf_counter(); fib_slow(25); print(f"slow: {time.perf_counter() - t:.3f}s")
t = time.perf_counter(); print(fib(90)); print(f"cached: {time.perf_counter() - t:.6f}s")

Common question

Is recursion just a trick for showing off?

Recursion means solving a problem by solving smaller versions of the same problem until one is trivial. It fits data that is itself recursive (trees, nested structures, grammars) and that split the input, such as merge sort and binary search. There, the recursive version is shorter and more obviously correct than any loop.

Always write the base case first and make sure every recursive call moves toward it. Keep the depth tied to the shape of the data, not its size; for flat sequences use a loop. When the same subproblems come up repeatedly, memoise with functools.cache so each is solved once.

Source: A tree is defined in terms of smaller trees, so the natural way to one is a function defined in terms of itself.

Common mix-ups

Each of these sounds reasonable. Think about why it is wrong, then open the explanation.

Any recursive function can be written as a loop, so recursion adds nothing.
Recursion is always slower than a loop.
A recursive function should call itself first and handle the base case last.

Practice

Write power_set(items) that returns every subset of a as a list of , using recursion: the subsets of [x, *rest] are the subsets of rest, plus each of those with x added.

Exercise

All subsets

3 checks

def power_set(items):
    ...


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

Output

Press Run to try your code, then Check answer to grade it.

Write depth(value) that returns how deeply nested a JSON-like value is: a non-container is 0, a list or dict is 1 plus the maximum depth of its contents (an empty container is 1).

Exercise

Nesting depth

3 checks

def depth(value):
    ...


print(depth(3), depth([]), depth([1, [2, [3]]]), depth({"a": {"b": [1]}}))

Output

Press Run to try your code, then Check answer to grade it.

Check yourself

Quick check

What is wrong with this function? def count_down(n): print(n); count_down(n - 1)

Finished reading?2 exercises still open. You can come back to them later.

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