Recursion often yields concise, elegant solutions. Unfortunately, most widely used languages limit how large your program stack can grow. So what do you do if you have a recursive algorithm but need to be able to run it without growing your stack? In this post, we'll see a generic way to take any recursive algorithm and convert it into an iterative one.

We'll do this in JavaScript, so you can run the code examples right in your browser.

An example problem: Binary tree depth🔗

Let's say we have a binary tree made up of nodes that have a left member and a right member. We want to find the length of the longest path from the root to one of the leaves. For example, the sketch below shows a tree with a depth of three, with its longest path highlighted.

A simple tree

We can build this tree using the following code.

const f = {val: 'f'};
const d = {val: 'd'};
const e = {val: 'e', right: f};
const b = {val: 'b', left: d, right: e};
const c = {val: 'c'};
const a = {val: 'a', left: b, right: c};

Later on we will programmatically generate much larger trees to intentionally cause a stack overflow. This will be sufficient to get started with.

Let's write a function that returns the depth of a tree:

function depth(node) {
    let d = 0;
    if (node.left) {
        d = 1 + depth(node.left);
    }
    if (node.right) {
        d = Math.max(d, 1 + depth(node.right));
    }
    return d;
}

Result:

If you click the "Run" button above, you should see "3" appear next to "Result." That means it's working!

Blowing the Stack🔗

Our code so far works for small trees, and probably even medium size trees. Let's see if we can break it though.

We could type out a very deep tree, but this would take a long time. Instead, let's generate one. This is a case where I would normally use recursion, but in this case our goal is to make a tree so big that we can't use recursion on it. Can recursion create a tree so big that can't be recursed on?

Instead, we'll start with an iterative algorithm to create a large tree using an explicitly managed stack. We could use the same recursion→iteration technique from this post, but let's not get ahead of ourselves.

The function below creates a tree of a given depth, eventually. It works by building a stack of tree nodes and transforming by one of several options. The first option is to push a new leaf node onto the stack. You can always do this, although we disable the choice when the stack is bigger than the desired depth to make sure the algorithm terminates eventually. The next to options are to pop the last node and make this either the left or right subtree of a new node. These options are allowed when the stack has depth at least 1. The final option takes the top two nodes off the stack and makes one the left and the other the right subtree of a new node. In each case, we store the depth of the tree on the node to make it obvious when we've made one of the right depth.

function makeTree(depth) {
    let stack = [];

    const options = [
        // Push a node with no children
        function push_leaf() {
            stack.push({depth: 0});
        },

        // Pop the last node and push a new one with only a left child
        function reduce_left() {
            let child = stack.pop();
            stack.push({depth: 1 + child.depth, left: child});
        },

        // Pop the last node and push a new one with only a right child
        function reduce_right() {
            let child = stack.pop();
            stack.push({depth: 1 + child.depth, right: child});
        },

        // Pop the last node and push a new one with only a right child
        function reduce_left_right() {
            let left_child = stack.pop();
            let right_child = stack.pop();
            stack.push({depth: 1 + Math.max(left_child.depth, right_child.depth),
                        left: left_child,
                        right: right_child});
        }
    ];

    while (true) {
        const min_option = stack.length < depth ? 0 : 1;
        let num_options = 1;

        if (stack.length >= 1) { num_options += 2; }
        if (stack.length >= 2) { num_options += 1; }

        let choice = min_option + Math.floor(Math.random() * (num_options - min_option));
        options[choice]();

        if (stack[stack.length - 1].depth >= depth) {
            return stack.pop();
        }
    }
}

You can use the buttons below to test generating trees of the given depth. After generating the tree, it runs our depth function from above on the resulting tree and displays the result. If everything works right, the result should be the same as the depth of the generated tree, so for example, makeTree(10) should evaluate to 10.

On my machine, Chrome failed on the 10,000 and 20,000 versions with RangeError: Maximum call stack size exceeded. This is what I was hoping to cause. I got different behavior on other browsers though. Firefox, for example, handled the 20,000 case without trouble. It'd be interesting to dive into why.

Staying Within the Stack🔗

Now that we've seen how to overflow the stack, it's time to rewrite our original depth function to limit its stack usage. Most recursive algorithms have iterative variants, which end up looking similar to our makeTree function -- that is, they use a stack data structure rather than the program stack. Our goal is to come up with a step by step process that will work for any piece of code without having to think too hard. The process we'll use is as follows:

  1. Convert the program to Continuation Passing Style
  2. Return thunks instead of making recursive calls
  3. Add an outer driver loop

This will work for JavaScript, since the language supports closures. In languages that don't support this, we can add an additional step:

  1. Convert thunks and continuations with data structures

This post will focus on the first three steps, and perhaps in a later post we can revisit step 4.

Step 1: Convert the program to Continuation Passing Style🔗

If we're doing to get rid of our program stack, we need to get ahold of it first. This is the magic of Continuation Passing Style (CPS). In CPS form, every function takes an extra argument, usually called k, which is a function that represents the rest of the function. CPS functions never return, but instead call their continuation. As an example, consider our basic recursive factorial function below.

function fact(n) {
    if (n == 0) {
        return 1;
    } else {
        return n * fact(n - 1);
    }
}

To convert this to CPS, we change fact(n) to be fact(n, k). Now, since functions never return, instead we replace all returns with a call to k. If we stopped here, we'd get:

function fact(n, k) {
    if (n == 0) {
        k(1);
    } else {
        k(n * fact(n - 1));
    }
}

We're done, right? Well... no. There are two problems. First, the recursive call to fact only has one argument, but we just rewrote our function to take two. The second problem is more subtle. Remember that in CPS form, functions never return? If fact(n-1) never returns, we'll never get to multiply the result by n, or call the continuation. Fortunately, we can solve both of these problems at once. For the second argument to fact, we need to package up everything left to do after the call. Notice that in our base case, we called k with what would have been the return value of fact, if fact returned. From this we see that continuations get an argument that is the return value of the function they were passed to. So looking at what's left to do, we need to take the return value of fact(n - 1), which we'll call v, multiply it by n, and then pass that to the original k. In code, that's v => k(n * v). We stick this function in for the second argument and now we have:

function fact(n, k) {
    if (n == 0) {
        k(1);
    } else {
        fact(n - 1, v => k(n * v));
    }
}

And we're good to go. Of course, there's some question about what to pass as k in the first place. We'll ignore that for now. Just pretend it's continuations all the way down.

Incidentally, this style of programming should be familiar to Node programmers. Node does asynchrony using callback functions. These callbacks represent what to do after the function is finished, which is exactly a continuation. In the same way that Node code tends towards arrow code, CPS code does as well, for the exact same reasons.

For some more detail about CPS, take a look at my older post on Continuation Passing Style Interpreters. That goes into some more depth, and shows how you can implement a powerful function called call/cc.

Now we return to the problem of transforming our depth function to CPS. This will be more complex than the factorial example for a couple of related reason. First, depth has side effects (the assignments to d). Second, depth makes multiple recursive calls. Third, depth has control flow that splits and joins (for example, you can get to the depth(node.right) call either by first calling depth(node.left) or by not doing the first recursive call). In other words, fact's control flow graph (CFG) is a tree, while depth is not1.

We'll walk through two different approaches. The first is to convert fact's CFG to a tree by duplicating code. I think this is conceptually simpler, but duplicating code makes me sad. The second option we'll consider avoids duplicating code by simulating GOTO.

Approach 1: Tree-structured Control Flow🔗

In our case, an easy way to make sure our control is tree-structured is to make sure every branch of an if ends in a return. We can do this with some pretty mindless copy and paste:

function depth(node) {
    let d = 0;
    if (node.left) {
        d = 1 + depth(node.left);
        if (node.right) {
            return Math.max(d, 1 + depth(node.right));
        }
        return d;
    }
    if (node.right) {
        return Math.max(d, 1 + depth(node.right));
    }
    return d;
}

To make this a little easier to convert to CPS, lets take one more step and lift out the recursive calls to depth.

function depth(node) {
    let d = 0;
    if (node.left) {
        let v = depth(node.left);
        d = 1 + v;
        if (node.right) {
            let v = depth(node.right);
            return Math.max(d, 1 + v);
        }
        return d;
    }
    if (node.right) {
        let v = depth(node.right);
        return Math.max(d, 1 + v);
    }
    return d;
}

Now to convert to CPS we can pull everything after the call to depth into a function that becomes the continuation argument to depth. Here's the result.

function depth(node, k) {
    let d = 0;
    if (node.left) {
        return depth(node.left, v => {
            d = 1 + v;
            if (node.right) {
                return depth(node.right, v => {
                    return k(Math.max(d, 1 + v));
                });
            }
            return k(d);
        });
    }
    if (node.right) {
        return depth(node.right, v => {
            return k(Math.max(d, 1 + v));
        });
    }
    return k(d);
}

Now we can test this out by supplying an initial continuation:

depth(node, v => v);

I tried this out on a couple of our examples so far, and it works as expected. Let's move on to our second approach.

Approach 2: Simulating GOTO🔗

We could avoid duplicating code by using GOTO. JavaScript doesn't have GOTO because it's considered harmful, but fortunately we do have Lambda, the ultimate GOTO.

Our approach will be to put functions around any place we might want as the target of a GOTO. Take a look at the CFG drawn below. The arrows represent places we would want a GOTO. In cases where two arrows leave a block, this means the block ends in a conditional branch. If the if condition was true, we go left, otherwise we go right.

CFG of depth()

Even though we don't have GOTO, we'll approximate this using functions. Instead of labels, we'll introduce new functions. Instead of GOTO, we'll insert a return of a function call (i.e. a call in tail position). As a first attempt, we get the following:

function depth(node) {
    let d = 0;
    if (node.left)
        return labelA();
    else
        return labelB();

    function labelA() {
        d = 1 + depth(node.left);
        return labelB();
    }

    function labelB() {
        if (node.right)
            return labelC();
        else
            return labelD();
    }

    function labelC() {
        d = Math.max(d, 1 + depth(node.right));
        return labelD();
    }

    function labelD() {
        return d;
    }
}

So far so good. There's actually a small optimization we can make. Notice how labelA and labelC are only called in one place? In other words, in the CFG, the nodes corresponding to labelA and labelB only have one incoming edge. We can take advantage of this to inline their bodies into their call site. The result is something a little more similar to our original code:

function depth(node) {
    let d = 0;
    if (node.left) {
        d = 1 + depth(node.left);
        return labelB();
    } else
        return labelB();

    function labelB() {
        if (node.right) {
            d = Math.max(d, 1 + depth(node.right));
            return labelD();
        } else
            return labelD();
    }

    function labelD() {
        return d;
    }
}

We can go further though. Even if there is more than one incoming edge, we can inline the function by duplicating its body. The labelD function is pretty simple, so lets go ahead and inline it away too:

function depth(node) {
    let d = 0;
    if (node.left) {
        d = 1 + depth(node.left);
        return labelB();
    } else
        return labelB();

    function labelB() {
        if (node.right) {
            d = Math.max(d, 1 + depth(node.right));
            return d;
        } else
            return d;
    }
}

Now we're at a good point to do our CPS transform. We'll give each of our functions a new continuation argument k, and each return value gets wrapped in a call to k. We create continuations for the calls to depth in a similar way.

function depth(node, k) {
    let d = 0;
    if (node.left) {
        return depth(node.left, v => {
            d = 1 + v
            return labelB(k);
        });
    } else
        return labelB(k);

    function labelB(k) {
        if (node.right) {
            return depth(node.right, v => {
                d = Math.max(d, 1 + v);
                return k(d);
            });
        } else
            return k(d);
    }
}

By lines of code, this version and the previous CPS version are about the same. To me this version is cleaner, in part because we did not have to duplicate any of the calls to depth. We'll use this version for the remainder of this post.

Step 2: Return thunks instead of making recursive calls🔗

So far we've rewritten our code with a bunch of extra functions and returns, but we still haven't solved the original problem. There is still a lot of recursion, and we'll still blow our stack. This is the step where we get rid of that.

Instead of calling our function, instead we want to delay the function and call it later. We do this by wrapping the call in a thunk. This is a very mechanical process. We basically just need to find any place where there is a return and insert a () => between the return and the function call.2 The result is below.

function depth(node, k) {
    let d = 0;
    if (node.left) {
        return () => depth(node.left, v => {
            d = 1 + v
            return () => labelB(k);
        });
    } else
        return () => labelB(k);

    function labelB(k) {
        if (node.right) {
            return () => depth(node.right, v => {
                d = Math.max(d, 1 + v);
                return () => k(d);
            });
        } else
            return () => k(d);
    }
}

Unfortunately, when I type this into the JavaScript console, I get this:

> depth(node, v => v);

function depth()

We were looking for a number, not a function. Instead, we need to keep calling the result until it gives us a number. I did this on our example tree from the beginning and got this:

> depth(a, v => v)()()()()()()()()()()()()()()()()()

3

So we had to call the function 17 more times to get a result. This is tedious, but lucky for us, computers are good at doing the same thing over and over again.

Step 3: Add an outer driver loop🔗

This is the last step. We're going to wrap our CPS and thunkified version of our depth function in a driver loop that will let us run without ever running out of stack space.

The heart of the idea is to call depth once to start the computation, and then keep calling the resulting thunk. Basically:

let thunk = depth(node, v => v);
while (true) {
    thunk = thunk();
}

This doesn't quite work though. The problem is that when we call the initial continuation (v => v), the result will be a number instead of a function and we'll get an error when we try to call it. There are a couple of ways around it. We could check if the thunk is still a function before we call it. This works here, but what if our computation were supposed to return a function at the end?

We could abuse exceptions, kind of like this:

let thunk = depth(node, v => { throw v});
try {
    while (true) {
        thunk = thunk();
    }
} catch (v) {
    return v;
}

Again, this works in our simple example, but what if the intervening code had its own try blocks? How would we make sure not to interfere with those?

Instead, let's go with something simpler. We'll just have a flag that says whether we're done and make the initial continuation set the flag. This is the approach used below, which is also our final version of the code.

function depth(node) {
    function depthCps(node, k) {
        let d = 0;
        if (node.left) {
            return () => depthCps(node.left, v => {
                d = 1 + v
                return () => labelB(k);
            });
        } else
            return () => labelB(k);

        function labelB(k) {
            if (node.right) {
                return () => depthCps(node.right, v => {
                    d = Math.max(d, 1 + v);
                    return () => k(d);
                });
            } else
                return () => k(d);
        }
    }

    let done = false;
    let thunk = depthCps(node, v => {
        done = true;
        return v;
    });
    while (!done) {
        thunk = thunk();
    }
    return thunk; // thunk is the result of the computation now.
}

We've wrapped our CPS version of depth in a function named depth and now we have a version that we can call just like the original. A caller of this function wouldn't be able to tell the difference, except that they can use as large of a tree as they want and still not run out of stack space (as long as you don't run out of memory first). Try it for yourself!

Conclusion🔗

We've gone through a general technique for how to take any recursive program and transform it into an iterative program. While it's nice to know this is possible, it's likely to come at a fairly high performance penalty so you may not want to do this in practice.

There are some more variations on this theme that are possible. For example, we're relied on the fact that JavaScript has closures. What if we're in a language without first class functions? Additionally, there are a few more tricks we can do to optimize this. Perhaps we can explore some of these variations in another post.

1

Although fortunately depth's CFG doesn't have any cycles.↩

2

We can actually be a little more judicious here and avoid creating so many thunks. The main thing is to break recursive cycles. In our case, these are calls from depth back to depth. We only have to insert a thunk somewhere along each cycle in the call graph. For simplicity, we've just done the simple version here.↩