Recursion

Ridgeline's holiday range includes gift boxes, and some gift boxes contain smaller boxes: the Explorer box holds two bags of coffee and a Brewing Kit, and the Brewing Kit holds a mug, a filter set and a sample bag. To price the Explorer box, you price everything inside it, and to price the Brewing Kit inside it, you price everything inside that. The problem contains smaller copies of itself. Recursion is the technique of solving a problem like this by having a function call itself on the smaller pieces.

Recursion is the natural tool for nested data such as gift boxes, folders and the trees of lesson 9, and for divide-and-conquer algorithms such as the binary search of lesson 7 and the merge sort of lesson 8. This lesson explains how recursive functions are built, what happens on the call stack while they run, how to keep them from running forever or running out of stack, how memoization makes some of them dramatically faster, and when an ordinary loop is the better choice.

Base case and recursive case

A recursive function has two parts. The base case is a version of the problem small enough to answer directly, without another call. The recursive case breaks the problem into a smaller version of the same problem, calls the function on it, and uses the result. Every recursive call must move closer to a base case; otherwise the calls never stop.

Counting down to a roast is the simplest example. To count down from n, print n and then count down from n - 1; the base case is reaching zero. A slightly more useful example adds up a list: the total of an empty list is 0 (the base case), and the total of any other list is its first item plus the total of the rest (the recursive case).

def countdown(n):
    if n == 0:                       # base case
        print("Drop the beans!")
        return
    print(n)
    countdown(n - 1)                 # recursive case: a smaller problem

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

countdown(3)
print(total([18.5, 22.0, 19.75]))

3
2
1
Drop the beans!
60.25

The total function is a teaching example, not good practice: the slice prices[1:] copies the list on every call, making it O(n²), and sum(prices) is simpler and faster. Recursion earns its place on problems whose shape is recursive, like gift boxes inside gift boxes, rather than on flat lists.

The call stack

Each time a function is called, Python creates a frame holding that call's local variables and the place to return to, and pushes it onto the call stack, the stack you met in lesson 3. When the function returns, its frame is popped and the caller carries on. During recursion, the stack holds one frame per unfinished call: factorial(4) waits for factorial(3), which waits for factorial(2), and so on down to the base case. Then the answers flow back up as the frames pop.

def factorial(n, depth=0):
    pad = "  " * depth
    print(f"{pad}factorial({n}) called")
    if n <= 1:
        print(f"{pad}base case returns 1")
        return 1
    result = n * factorial(n - 1, depth + 1)
    print(f"{pad}factorial({n}) returns {result}")
    return result

factorial(4)

factorial(4) called
  factorial(3) called
    factorial(2) called
      factorial(1) called
      base case returns 1
    factorial(2) returns 2
  factorial(3) returns 6
factorial(4) returns 24

Because every unfinished call holds a frame, deep recursion uses memory, and Python sets a recursion limit, normally 1,000 frames, to stop a runaway recursion from crashing the interpreter. Exceeding it raises RecursionError. Missing or unreachable base cases are the usual cause; a correct recursion that simply goes very deep, such as walking a linked list of 10,000 nodes, is better written as a loop.

import sys

def no_base_case(n):
    return no_base_case(n + 1)       # never stops

print("limit:", sys.getrecursionlimit())
try:
    no_base_case(0)
except RecursionError as e:
    print("RecursionError:", e)

limit: 1000
RecursionError: maximum recursion depth exceeded

Recursion on nested data

Recursion is at its best with data that nests to any depth, because a loop alone cannot know how many levels to descend. Ridgeline's gift boxes are stored as dictionaries: a simple product has a price, and a box has a list of contents, which may themselves be boxes. The price of a box is the sum of the prices of its contents, and the function that computes it simply calls itself on each item inside.

explorer = {
    "name": "Explorer box",
    "contents": [
        {"name": "Sunrise Blend", "price": 18.50},
        {"name": "Ethiopia Guji", "price": 22.00},
        {"name": "Brewing Kit", "contents": [
            {"name": "Ridgeline mug", "price": 14.00},
            {"name": "Filter set", "price": 9.50},
            {"name": "Sample bag", "price": 6.00},
        ]},
    ],
}

def price(item):
    if "price" in item:                       # base case: a single product
        return item["price"]
    return sum(price(part) for part in item["contents"])

def show(item, depth=0):
    print("  " * depth + f"{item['name']}: {price(item):.2f}")
    for part in item.get("contents", []):
        show(part, depth + 1)

show(explorer)

Explorer box: 70.00
  Sunrise Blend: 18.50
  Ethiopia Guji: 22.00
  Brewing Kit: 29.50
    Ridgeline mug: 14.00
    Filter set: 9.50
    Sample bag: 6.00

Look how little code is needed: the function handles one level and trusts the recursive call to handle everything below. That trust, sometimes called the recursive leap of faith, is the key mental habit. To check a recursive function, confirm that the base case is right, that each call works on something smaller, and that the result is correctly built from the answers to the smaller calls. The same pattern walks folders on disk, JSON documents and the trees of lesson 9.

def count_products(item):
    return len(item.get('contents', []))

print(count_products(explorer))

Divide and conquer

Many of the fastest algorithms are recursive because they divide a problem into halves, solve each half recursively and combine the results. This strategy is called divide and conquer. Finding the highest sale in a list can be done that way: the maximum of a list is the larger of the maximum of its left half and the maximum of its right half, and a list of one item is its own maximum. Each level of recursion halves the problem, so there are about log₂ n levels.

def biggest(sales, lo=0, hi=None):
    if hi is None:
        hi = len(sales) - 1
    if lo == hi:                              # one item: it is the biggest
        return sales[lo]
    mid = (lo + hi) // 2
    return max(biggest(sales, lo, mid), biggest(sales, mid + 1, hi))

day = [18.5, 44.0, 5.25, 61.75, 22.0, 9.5, 37.0]
print(biggest(day), max(day))

61.75 61.75

Passing lo and hi indexes instead of slicing avoids copying the list on every call, a technique you will use again in binary search and merge sort. For a simple maximum, the built-in max is still the right choice; the value of the example is the shape of the solution, which lessons 7 and 8 turn into genuinely faster algorithms.

Memoization

Some recursive functions solve the same smaller problems over and over. Kai packs roasted coffee into bags of 1, 2 or 5 kilograms for wholesale customers and wants to know how many different sequences of bags make up a given order weight. The number of ways to make n kilograms is the number of ways to make n - 1 (then add a 1 kg bag), plus the ways to make n - 2, plus the ways to make n - 5. Written directly, that recursion recomputes the same values exponentially many times.

Memoization stores the answer to each subproblem the first time it is computed and looks it up afterward. The functools.cache decorator, a simpler form of the lru_cache you met in PYTH-102, does it automatically by keeping a dictionary from arguments to results. The listing counts how many calls each version makes.

import functools

calls = 0
def ways_slow(n):
    global calls
    calls += 1
    if n < 0:
        return 0
    if n == 0:
        return 1
    return ways_slow(n - 1) + ways_slow(n - 2) + ways_slow(n - 5)

@functools.cache
def ways(n):
    if n < 0:
        return 0
    if n == 0:
        return 1
    return ways(n - 1) + ways(n - 2) + ways(n - 5)

print(ways_slow(20), "using", calls, "calls")
print(ways(20), "using", ways.cache_info().misses, "distinct computations")
print(ways(200))

26547 using 112981 calls
26547 using 25 distinct computations
13487966597824560643006952047078537117138130993

The slow version makes tens of thousands of calls for n = 20 and would need longer than the age of the universe for n = 200; the memoized version computes each value once, so n = 200 takes about 200 steps. This idea of solving each overlapping subproblem once is called dynamic programming, and it can also be written bottom-up with a loop that fills a list from the smallest case upward, avoiding deep recursion altogether.

import functools

@functools.cache
def ways(amount):
    if amount <= 0:
        return 1
    return ways(amount - 5) + ways(amount - 10) + ways(amount - 25)

print(ways(10))

Recursion or a loop?

Anything written recursively can be written with a loop and, if needed, an explicit stack, and anything written with a loop can be written recursively. Choose by clarity and by depth. Recursion is clearer for nested structures and divide-and-conquer algorithms, where the depth is modest: a balanced tree of a million items is only about 20 levels deep. A loop is better for long linear processes, such as walking a linked list or counting down from a large number, where recursion would use one frame per step and hit the recursion limit. Unlike some languages, Python does not optimize tail calls, so even a recursive call in the last position of a function uses a new frame.

def price_iterative(item):
    """The gift-box price with an explicit stack instead of recursion."""
    total, stack = 0.0, [item]
    while stack:
        current = stack.pop()
        if "price" in current:
            total += current["price"]
        else:
            stack.extend(current["contents"])
    return total

box = {"contents": [{"price": 18.5}, {"contents": [{"price": 14.0}, {"price": 9.5}]}]}
print(price_iterative(box))

42.0

def folder_size(folder):
    return sum(v for v in folder.values() if isinstance(v, int))

photos = {'logo.png': 120, 'coffees': {'rc-101.jpg': 850, 'rc-102.jpg': 910}}
print(folder_size(photos))