Learning Python, Part 6: Recursion, Searching and Classes

The last part pulls together three ideas that make programs bigger without making them harder to follow: functions that call themselves, searching efficiently, and bundling data with the code that uses it.

Recursion

A recursive function solves a problem by solving a smaller version of the same problem. Every recursive function needs two parts:

A base case that is answered directly, with no further calls.
A recursive case that calls the function on something strictly smaller, then uses that answer.

def digit_sum(n):
    if n < 10:                          # base case: one digit
        return n
    return n % 10 + digit_sum(n // 10)  # last digit + the rest

print(digit_sum(4081))    # 13

n % 10 peels off the last digit and n // 10 is everything before it. Each call works on a shorter number, so the calls must eventually reach the base case.

How to write one

Write the base case first. Ask: what is the smallest input, and what is its answer?
Then assume the function already works for smaller inputs, and ask how to turn that answer into yours.
Check that every recursive call moves towards the base case. If it does not, you get a RecursionError once Python reaches its call-depth limit, roughly a thousand calls by default.

Order of work matters

Compare two ways of building a string of digits in another base:

def digits(n, base):
    if n < base:
        return str(n)
    return digits(n // base, base) + str(n % base)

print(digits(13, 2))    # 1101

The recursive call returns the front digits and the last digit is attached afterwards. Reverse the concatenation and the digits come out backwards.

Recursion on nested data

Recursion is at its most natural when the data is itself nested, as with lists inside lists:

def count_leaves(box):
    total = 0
    for item in box:
        if isinstance(item, list):
            total += count_leaves(item)
        else:
            total += 1
    return total

print(count_leaves([1, [2, [3, 4]], [], 5]))    # 5

A loop alone cannot handle arbitrary depth without extra bookkeeping, but the function simply calls itself on each inner list.

Recursion versus iteration

Anything you can write recursively you can also write with a loop. The recursive version often reads more clearly when the problem has a self-similar shape. The loop is usually faster and has no depth limit. Be wary when a recursive function calls itself twice per step. The textbook example is a naive Fibonacci:

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

fib(30) makes well over a million calls, because it recomputes the same values again and again. A loop that keeps the last two values does the job in 30 steps.

Searching

Linear search checks each item in turn and stops when it finds a match. It works on any list, and in the worst case it looks at every item.

def linear_search(items, target):
    for i in range(len(items)):
        if items[i] == target:
            return i
    return -1

Binary search needs a sorted list. It looks at the middle item and throws away the half that cannot contain the target, then repeats on what is left.

def binary_search(items, target):
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        if items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

print(binary_search([2, 5, 9, 14, 20, 31], 14))   # 3

The saving is large. A list of a million items needs up to a million checks with linear search but at most about twenty with binary search, because a million can only be halved around twenty times. The price is that the list must be sorted first, and sorting costs time too.

Computer scientists describe this scaling informally: linear search grows in proportion to the list size, while binary search grows with the number of times the size can be halved. What matters at this level is the shape of the growth, not the exact timings.

Classes

A class bundles data and the functions that use it. An object made from a class is an instance, and the data it carries is its state.

class CoinJar:
    def __init__(self, goal):
        self.goal = goal
        self.coins = []

    def add(self, coin):
        self.coins.append(coin)

    def total(self):
        return sum(self.coins)

    def remaining(self):
        return max(0, self.goal - self.total())

jar = CoinJar(500)
jar.add(200)
jar.add(50)
print(jar.total(), jar.remaining())     # 250 250

__init__ runs when you create an object. It sets up the starting state.
self is the object the method was called on. It is passed automatically, so you write jar.add(200) but define add(self, coin).
Names like self.coins live in the instance. Two jars keep separate coins, because each __init__ makes a new list.
Methods can call each other, as remaining calls total.

A common mistake is to create the list at class level (coins = [] directly under class CoinJar:). That list is then shared by every jar, which is the same trap as the mutable default argument in Part 3.

Objects can hold other objects. A Wallet class could keep a list of CoinJar objects and ask each for its total. When you are designing a class, ask what it needs to remember and what questions or actions it should offer. The first answers become attributes and the second become methods.

Looking back

The series has covered values, control flow, functions, the built-in collections, errors and now structure. A few habits carry across all of it:

Trace small examples by hand before trusting code.
Test the edges: empty input, one item, the largest case, the bad input.
Prefer returning a new value over changing an argument.
Name the exception you expect.
Let the shape of the data suggest the shape of the code.

Where to practise

In Set A, the “Even digits on a ticket”, “Unpacking the gift boxes” and “How deep do the boxes go?” drills are recursion. In Set B, try “Door codes in other bases”, “Counting the museum” and “The busy rooms”, then build a class in “The pantry”. The drill checker flags a loop in the recursion drills.