6.101 Fall 2022: Recursion and Iteration

This reading examines recursion more closely by comparing and contrasting it with iteration. Both approaches create repeated patterns of computation. Recursion produces repeated computation by calling the same function recursively, on a simpler or smaller subproblem. Iteration produces repeated computation using for loops or while loops.

If we can come up with an iterative version, do we need recursion at all? In one sense, no, we don’t need recursion – any function we can write recursively could also be written iteratively. But some problems lend themselves naturally to a recursive solution. When we try to solve those kinds of problems iteratively instead, we find ourselves simulating recursion anyway, using an explicit agenda to keep track of what we need to do next. For those kinds of problems, it’s more straightforward to express the recursive algorithm directly, letting Python handle the agenda bookkeeping using its call stack.

The converse is also true: any function we can write iteratively, with a loop, could also be written recursively. So it’s important to be able to think in both ways and choose the one that is most natural and appropriate to the problem we are trying to solve.

This reading looks at the essential equivalence between these approaches and some of their tradeoffs in simplicity and performance. We’ll return to some of the functions we’ve written in previous readings, both recursive and iterative, and show how to write them using the respective other techniques.

Let’s start with the simple example we used in the last reading: factorial. Mathematically, we could have used either of the following definitions of factorial:

or

The first definition is recursive, but the second is actually iterative – it doesn’t mention $\mathrm{<p>n</p>}<p>!</p>$ on the right-hand side of the definition, and the right-hand side effectively describes a loop.

In terms of code, these definitions translate directly to either a recursive or iterative implementation:

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

def factorial(n):
    out = 1
    for i in range(1, n+1):
        out *= i
    return out

Here are some points of comparison:

• The iterative version might be more efficient, because it doesn’t need to create new frames for the recursive calls.
• The recursive version might feel simpler, a better match for the mathematical definition of factorial.
• The two versions might behave differently with illegal inputs, like $\mathrm{<p>n</p>}<p><</p>\mathrm{<p>0</p>}$.

For either version, it would be better if the function produced an error right away when it gets an illegal input:

def factorial(n):
    assert n >= 0, "need a nonnegative integer"
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

The result of factorial(-1) for the recursive version points at an important difference between recursion and iteration in many programming languages (including Python): recursion is limited by a maximum call-stack depth. In Python, this default limit is 1000 calls. When a function tries to call deeper than that, Python produces RecursionError. This limit can be increased using sys.setrecursionlimit(), but it can’t be made unbounded, because the operating system itself puts a limit on Python’s call stack.

The rest of this reading is structured by looking at several common kinds of repeated computation, depending on the shape of the data it is processing: list-like (i.e., a sequence of values), tree-like, and graph-like. We will reach back to previous readings for a recursive or iterative algorithm that we have previously looked at for each of these forms, discussing how we might write the algorithm the other way.

Let’s start with lists. Recall sum_list from the Recursion reading, which we wrote both iteratively and recursively:

def sum_list(x):
    sum = 0
    for num in x:
        sum += num
    return sum

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

The iterative version naturally uses a for loop.

The recursive version decomposes the list into its first element x[0] and the rest of the list x[1:]. The rest-of-list part is the smaller recursive subproblem. This first/rest decomposition is a very common way to deal with list-like data recursively.

Notice that in each of these decompositions, the algorithm must be careful to make the recursive subproblems smaller. The first/rest and middle/left/right decompositions do it by peeling off one element of the list (the first or the middle) and excluding it from the recursive subproblems, so that they are definitely smaller than the original problem. This is how these decompositions guarantee that the subproblems are smaller than the original problem, so we will eventually terminate at the base case (which is often, but not always, the empty list).

Accumulating Results Using a Helper Function

def sum_list(x):
    def sum_helper(sum, lst):
        if not lst:
            return sum
        else:
            num = lst[0]
            rest = lst[1:]
            return sum_helper(sum + num, rest)
    return sum_helper(0, x)

def sum_list(x):
    sum = 0           # becomes initial call to sum_helper(0, x)
    for num in x:     # becomes num = lst[0], rest = lst[1:]
        sum += num    # becomes recursion step sum_helper(sum+num, rest)
    return sum        # becomes the base case

def sum_list(x, sum=0):
    if not x:
        return sum
    else:
        return sum_list(x[1:], sum + x[0])

Optimizations

Having examined sequential, list-like data, let’s turn now to tree-shaped data, which might go to arbitrary depth. For example, recall sum_nested from the Recursion reading:

def sum_nested(x):
    """
    >>> sum_nested([[1, 2], [3, [4, 5]], [[[[[6]]]]]])
    21
    """
    if not x:
        return 0
    elif isinstance(x[0], list):
        return sum_nested(x[0]) + sum_nested(x[1:])
    else:
        return x[0] + sum_nested(x[1:])

Why do we think of the input to sum_nested as tree-shaped? Because each sublist in x is like an internal node of a tree, with children that might be further sublists, until we reach simple numbers, which are the leaves.

Tree-shaped data has a straightforward recursive decomposition that mirrors the tree structure: we make recursive calls to all children.

But notice that sum_nested as written here is not only decomposing the tree structure recursively but also decomposing the list of children recursively.

To convert this recursive function into an iterative loop, we will reach back to an idea that we used in earlier readings: an agenda. Here, our agenda will keep track of recursive calls that we haven’t made yet. Specifically, each item on the agenda will consist of the parameters for a recursive call. The agenda is initialized with the original list (which we will rename to original_x so that we can keep using x for the rest of the code without confusion), and then every time we encounter a recursive call to sum_nested(), we put it on the agenda instead, so that it will be handled in a later iteration of the loop. Here is the code:

def sum_nested(original_x):
    sum = 0
    agenda = [original_x] # agenda consists of parameters for pending recursive calls
    while agenda:
      x = agenda.pop(0)
      if not x:
          sum += 0
      elif isinstance(x[0], list):
          agenda.insert(0, x[0])
          agenda.insert(0, x[1:])
      else:
          sum += x[0]
          agenda.insert(0, x[1:])
    return sum

We opted in this iterative implementation to add and remove items at the start of the agenda, so that it explores the tree in the same order that the recursive algorithm does – depth-first. But we didn’t necessarily have to make that choice – how could we change the code so that the iterative version is traversing the tree breadth-first instead? Either way, it doesn’t matter for sum_nested, since the numbers can be added in any order, but for other problems, the order might matter.

Looking at the transformation we just did from the other point of view, there is an agenda data structure hiding inside the recursive version – the agenda is just the call stack, managed by Python, and keeping track of the remaining work that needs to be done in the recursive process. So recursion gives us a convenient and simple way to express a depth-first traversal without having to manage our own agenda data structure.

Now that we have explored the equivalence between recursive traversal and iterative (depth-first) traversal using an explicit agenda, let’s go back to graph-traversal problems we explored in earlier readings. “Graph-like” data can be regarded as vertices connected by edges, but (unlike a tree) a graph may have multiple paths reaching the same vertex, or it may have cycles (paths that return to the same vertex again).

In previous readings, we solved graph-traversal problems using iteration, like this flood-fill function:

def flood_fill(image, starting_location, new_color):
    original_color = get_pixel(image, *starting_location)
    agenda = [starting_location]  # agenda: all of the cells we need to color in
    visited = {starting_location}  # visited set: all pixels ever added to the agenda
    while agenda:
        location = agenda.pop(0)
        set_pixel(image, *location, new_color)
        for neighbor in get_neighbors(location):
            if (neighbor not in visited
                    and get_pixel(image, *neighbor) == original_color):
                visited.add(neighbor)
                agenda.append(neighbor)

Now that we know that we can use the recursive call stack as an agenda, how can we write this recursively? Everywhere we would put a work item on the agenda, let’s make a call to a recursive helper function instead, using the work item as its parameter. This recursive helper function replaces the while loop:

def flood_fill(image, starting_location, new_color):
    original_color = get_pixel(image, *starting_location)
    visited = {starting_location}  # visited set: all pixels ever added to the agenda
    def fill_from(location):
        set_pixel(image, *location, new_color)
        for neighbor in get_neighbors(location):
            if (neighbor not in visited
                    and get_pixel(image, *neighbor) == original_color):
                visited.add(neighbor)
                fill_from(neighbor)
    fill_from(starting_location)

def flood_fill(image, starting_location, new_color):
    original_color = get_pixel(image, *starting_location)
    if original_color == new_color:
      return # nothing to do
    def fill_from(location):
        set_pixel(image, *location, new_color)
        for neighbor in get_neighbors(location):
            if get_pixel(image, *neighbor) == original_color:
                fill_from(neighbor)
    fill_from(starting_location)

How might you decide to use recursion?

• When the problem is easy to express recursively (as factorial)
• When the data itself is defined recursively (like a tree often is)
• When depth-first traversal is fine
• When the recursion won’t get too deep (this constraint may be relaxed for programming languages other than Python)

Recursive solutions are often shorter and simpler, by moving agenda bookkeeping into the programming language rather than representing it explicitly.

As you gain comfort with recursion, you may find that a recursive solution is easier to express at first, because of natural decompositions (like first/rest, or left-half/right-half, or recursing into children or graph neighbors). So it may be good to start with a recursive approach and then convert it to an iterative algorithm (using one of the strategies here) if you run into problems like recursion depth limits or excessive copying.

Here are three common ways that a recursion can go wrong:

• The base case may be missing entirely, or the problem needs more than one base case, but not all the base cases are covered.
• The recursive step doesn’t reduce to a smaller subproblem, so the recursion doesn’t converge.
• Aliases to a mutable data structure are inadvertently shared, and mutated, among the recursive calls.

We saw the first two issues in an exercise above, when we tried to convert sum_list to use a left/right decomposition. When the subdivided list reached length 1, the decomposition was no longer able to make two smaller subproblems, so we needed to make that into a new base case.

Aliases to mutable data are sometimes necessary in recursion, as we saw above when we shared the visited set across all calls in a recursive traversal of a graph. For flood fill, of course, sharing the mutable image is necessary, because the whole point of the recursion is to fill in more pixels. But when you are doing a recursive depth-first search without a visited set – which, as we saw with flood fill, is often possible when a move in the search automatically makes the problem smaller or simpler – it can be tempting to keep the search state mutable. This then becomes tricky, because then multiple pending recursive calls have aliases to the same mutable state. We will see an example of this in the next reading, when we use recursive search to solve Sudoku puzzles.

Look for these mistakes when you’re debugging. A RecursionError is a sign of the first two. The third bug can be harder to spot, because it’s fundamentally an aliasing bug.

We’ve explored several kinds of problem, based on the shape of the data or repeated computation that needs to be done (list-like, tree-like, graph-like), and seen how to do the repeated computation both recursively and iteratively.

Along the way, we’ve seen more strategies for thinking recursively, including:

• recursive decompositions that are commonly used for list-like data (first/rest, left-half/right-half), tree-like data (recursing into children), and graph-like data (recursing to neighbors);
• using a recursive helper function with parameters that accumulate partial results;
• using recursion for a depth-first traversal of a tree or graph.