Loops and Recursion

Recursion was a concept that took me a long time to understand. It wasn’t until years after I’d started programming that I felt I really understood it, and it wasn’t until years after that that I felt confident reaching for it as a tool. Like almost everyone, the first way that I learned to think of iteration was with loops. If you wanted to add something together, for example, you would create a “bookkeeping” variable and modify it inside the loop.

def add_range(start: int, end: int) -> int:
    total = 0
    for n in range(start, end + 1):
        total += n
    return total

It’s like writing down a number, looking at the next one, erasing the previous one, and writing down the new one. Recursion comes less naturally.

def add_range_rec(start: int, end: int) -> int:
    if start == end:
        return start
    else:
        return start + add_range_rec(start + 1, end)

Thinking recursively is more like saying “First, if I’ve reached this state, stop.¹ Otherwise, add the current number to the sum of all the other numbers.” Next, consider a simple linked list:

@dataclass
class Node:
    elem: Any
    rest: Optional["Node"] = None

    def push(self, elem):
        return Node(elem, rest=self)

We can construct the list using our push method:

xs = Node(5).push(10).push(15)
# Node(elem=15, rest=Node(elem=10, rest=Node(elem=5, rest=None)))

This is a simple “recursive data structure,” referring to itself as the type of one of its own properties (rest). The push method isn’t recursive or iterative, though, because it doesn’t need to be: pushing a value onto the head of a linked list is just a question of creating a new element with its rest pointing to the previously-existing list. If we wanted to find the last element, though, we have a choice. We can implement last iteratively, keeping track of which node we’re looking at,

def last(self):
    target = self.rest

    while target.rest is not None:
        target = target.rest

    return target.elem

or we can ask each node in turn for its last element.

def last_rec(self):
    if self.rest is None:
        return self.elem
    else:
        return self.rest.last_rec()

Something to realize from these examples is that both loops and recursion can express the same concepts.² Whether you write code iteratively or recursively, under the hood they are implemented with looping, and even at the high level you can always translate one to the other. Knowing that, you may wonder why you’d ever choose to express an algorithm recursively. The answer is simply that some algorithms are more naturally expressed recursively, treating each step as a “subproblem.”

Consider the famous problem, “How many ways are there to make change for $1?” Expressed as a series of subproblems, it’s actually relatively straightforward:

1. How do you make change for $1 using 50¢, 25¢ 10¢, 5¢, and 1¢?
2. How do you make change for 50¢ using 50¢, 25¢ 10¢, 5¢, and 1¢?
3. How do you make change for 75¢ using 25¢ 10¢, 5¢, and 1¢?
4. How do you make change for 90¢ using 10¢, 5¢, and 1¢?
5. How do you make change for 99¢ using 1¢?
6. …

This continues until you have counted each subproblem and totaled them up to the top level.

COINS = [50, 25, 10, 5, 1]

def make_change(amt, last=COINS[0]):
    if amt == 0:  # If the target amount is zero, count this as one path.
        return 1

    # Otherwise, recurse into the subproblems, one per valid coin.
    valid_coins = (c for c in COINS if c <= amt and c <= last)
    return sum(make_change(amt - c, c) for c in valid_coins)

By contrast, trying to implement this in an iterative style is a little more verbose. The best way is to use a stack; this is a common technique for translating recursive algorithms to iterative implementations. In essence, it trades function calls for a collection of actions to be taken, which is then handled with some manual bookkeeping.

def make_change_stack(amt):
    total = 0
    stack = [(amt, COINS[0])]

    while stack:
        amt, last = stack.pop()

        if amt == 0:
            total += 1
        else:
            valid_coins = (c for c in COINS if c <= amt and c <= last)
            stack.extend((amt - c, c) for c in valid_coins)

    return total

The last concept I want to introduce is “dynamic programming.” This is another concept that was confusing to me for a long time, because it was hard to pin down exactly what its proponents were arguing for; in fact, I went to a talk about it at a conference that remains, to this day, the single most incomprehensible talk I have ever attended. Eventually, I figured out that the general idea is “recursion with caching.” It’s extremely difficult to implement this in Python, as you must add an import statement and a decorator.

from functools import lru_cache

@lru_cache(maxsize=None)
def make_change(amt, last=COINS[0]):
    if amt == 0:
        return 1

    valid_coins = (c for c in COINS if c <= amt and c <= last)
    return sum(make_change(amt - c, c) for c in valid_coins)

Exercises

Just as I did in my post about symbolic logic, I offer several exercises here that will help you build your understanding of recursion (and loops, for that matter).

1. When you call a function recursively, it gets pushed into the “call stack.” Most languages have a limit on how deep this stack can be. Experiment to figure out how deep the stack is in Python (or your favorite language).
2. The @lru_cache decorator stores the results of a function for a given set of inputs. By how much does it decrease the number of calls to make_change compared to the uncached recursive version?
3. The @lru_cache strategy can’t be immediately applied to the stack-based implementation of make_change. However, a similar strategy can be used; implement it.
4. $\star$ Even in languages where the stack depth is relatively shallow, like Python, there are methods for implementing recursion safely. One of them is called a “trampoline.” Research and write an implementation.
5. $\star \star$ Using the disassembly tools in the dis module, compare the compiled bytecode of the stack- and recursion-based implementations of make_change. What differences do you note between the functions?