DS&A

Three Ways to Think About Recursion

Like all important ideas, recursion can be thought about in many ways, and there is no single “correct” or “best” way to think about it. Rather, each way of thinking is useful for some purposes, but not helpful in every situation.

In the posts about recursion on trees and linked lists, we thought about:

• What recursion is,
• How to find recursive structures in problems, and
• How to write simple recursive functions to solve those problems.

We haven’t yet thought about how recursive functions actually work — what happens when a recursive function is called? In this post we’ll see three different ways to think about how recursive functions are actually computed.

We’ll use each of these ways to understand how the tree sum example works. As a reminder, this example uses the following tree:

Here’s the function in Python:

def tree_sum(node):
    t = node.value
    for child in node.children:
        t += tree_sum(child)
    return t

“Leap of faith”

A recursive function calls itself. So, to compute a recursive function, we also have to compute the recursive calls to the same function, which make recursive calls themselves, and so on.

The simplest way to understand recursive functions is to ignore the recursive calls, and simply trust that they do the right thing; this way, we only need to think about one call at a time.

Use the buttons to compute the sum for Node #1 step-by-step. Notice that we don’t follow any of the steps it takes to recursively compute the sum for the child nodes — we take a “leap of faith” and trust that they will return the correct sum.

This is a good way of seeing why a recursive function gives correct results. But if we make a mistake in our code, the recursive calls will return incorrect results — so the “leap of faith” method is useless for debugging.

Call stack

Before we can think through recursive calls step-by-step, we need to understand how the computer keeps track of them. Functions can have parameters and local variables; these will have different values each time the function is called. If the function is recursive, there can be multiple “instances” of the same function, each of which must have its own memory to store its own variables.(1)

This interactive model works step-by-step through every recursive call, keeping track of which “instances” of the function are still being computed at each step.

The “instances” of a function are frames. Each time a function is called, the computer creates a new frame for that instance of the function. The caller must wait for the call to return; then the caller can continue.

In this example, the Node #1 frame needs the sum of Node #2, which needs the sum of Node #3. When that sum is returned, the Node #2 frame continues. When the Node #2 sum is returned, the Node #1 frame continues.

This is “last in, first out” behaviour — just like a stack. In fact, the computer does use a stack to keep track of function calls:

• When a function is called, a new frame is created with the appropriate inputs, and pushed onto the call stack.
• When it returns, that frame is popped off the stack, and the result it returns is given to the frame below it on the stack.

This applies whether or not the function is recursive, but the call stack is especially useful for understanding how recursive functions work.

Call tree

The call stack is dynamic — its contents keep changing as the program runs, because it only ever contains the currently “active” frames. This makes it hard to inspect unless we deliberately stop the program mid-execution.

When a frame is completed, it returns its result and then the frame is no longer needed for the computation, so the frame is discarded. However, thinking about all frames, including the completed ones, can help us understand the recursive function.

This interactive model is the same as the previous one, except the completed frames aren’t discarded:

The frames for all of the function calls form a tree — the “root node” is the original function call, a frame’s “parent” is the frame which called it, and a frame’s “children” are the frames for the recursive calls it makes.(2)

Thinking about the call tree is useful for debugging — sometimes we debug a function by printing some information when it’s called, and this means we’ll see the printed output for every call, not just the ones which are currently “active” at any particular time. Consider the modified tree_sum code below:

def tree_sum(node):
    print('Called with node value', node.value)
    t = node.value
    for child in node.children:
        t += tree_sum(child)
    print('Returned', t)
    return t

This function will print the following output. With appropriate indentation, it shows the call tree structure as an outline:

Called with node value 1
Called with node value 2
Called with node value 3
Called with node value 4
Returned 4
Called with node value 5
Returned 5
Returned 12
Called with node value 6
Returned 6
Returned 20
Called with node value 7
Called with node value 8
Called with node value 9
Returned 9
Returned 17
Returned 24
Called with node value 10
Returned 10
Returned 55

Call trees are also useful for thinking about efficiency — the number of frames in the call tree is equal to the number of times the function was called. We can use this idea to estimate how much time it would take to compute a recursive function with various inputs.

Footnotes

1. Otherwise, a recursive call would overwrite the values of the original call’s variables.
2. This model shows the call tree as an icicle diagram.

• Tags: 
• recursion