# How to Convert Recursion to Iteration

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.

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:

- Convert the program to Continuation Passing Style
- Return thunks instead of making recursive calls
- 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:

- 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
not^{1}.

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.

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.โฉ