Fear Not Recursion

Recursion is… Feared?

I've observed that there exists an aversion to recursion in that most well-known programming languages (think C, C++, Java) are iterative in nature. Recursion is framed as inefficient, but a necessary and elegant evil for certain categories of problems. It also doesn't help that it's sometimes touted as a complete replacement for iteration in languages that have looping constructs in the first place!

Iteration and recursion can coexist, and this is proven elegantly by algorithms such as Pratt Parsing. Recursion should not signal "inefficient" just as much iteration should not signal "inelegant". In languages where they're both available, they are equally valid tools for solving problems.

In the absence of iteration at the language level, such as in functional programming, recursion proves to be the next best thing for modeling repeated computation.

Does this mean that functional programming languages, while elegant, are inefficient because they lack loops? Absolutely not! Just as you have optimization techniques for procedural/iterative code, optimizations for functional/recursive code have also been developed over the years specifically through language research.

The Call Stack

When a function is called, the compiler or language runtime needs to keep track of where to resume execution once said function finishes. One such mechanism that's used for this is the call stack.

The call stack consists of information pertinent to the execution of a function separated in frames; this information may include arguments, space for local variables, and most importantly, a return address which tells the runtime where it should resume execution.

For example, the following chain of functions:

function first() {
    let a = second();
    let b = third();
    return a + b;
}

May produce the following call stack over time:

               .--------.     .--------.
               | second |     | third  |
.--------. >=> +--------+ >=> +--------+ >=> .--------.
| first  |     | first  |     | first  |     | first  |
+--------+     +--------+     +--------+     +--------+

The call stack usually has an upper limit defined by either the runtime or hardware constraints. When this upper limit is reached, a stack overflow occurs.

With this idea in mind, one case that can be made against recursion is that it's easy for recursive algorithms to blow up the call stack, and that case is right for most of the time.

As I've mentioned however, a lot of optimization techniques have been developed in the decades before that specifically deal with these problems.

Tail-Call Optimization

Tail-call optimization refers to a common technique performed by compilers wherein a "tail call" can reuse the current stack frame rather than allocating an entirely new one.

But… what are tail calls and why can they be optimized? In simple terms, tail calls are function calls that occur as the final action within a function.

The most basic example could be something like:

function first() {
    if (condition) {
        return second();
    } else {
        let a = third();
        let b = fourth();
        return a + b;
    }
}

We can determine that the second function occurs as a final action within a branch in the function, therefore being a tail call; meanwhile, neither third nor fourth are tail calls since they're executed one after the other, after which their results are added and returned.

Tail-Call Recursion

Tail-call recursion refers to when a recursive call appears in the tail position, which allows tail-call optimization to kick in and optimize execution for the function.

Rather than allocating more stack frames for the recursive calls, which could potentially cause a stack overflow, recursive calls can simply reuse the stack frame for the current call.

Let's take a look at how this can be applied with the factorial function:

function factorial(n: number): number {
    if (n == 0 || n == 1) {
        return 1;
    } else {
        let n_1 = factorial(n - 1);
        return n * n_1;
    }
}

Here, we can see that the recursive call to factorial(n - 1) doesn't appear in the tail position, since the result has to then be multiplied with n. This entails a call stack that grows relatively to how high the given value is.

To take advantage of tail-call optimization, we can reformulate the factorial function into a tail-recursive definition such as:

function factorial(n: number, a: number): number {
    if (n == 0 || n == 1) {
        return a;
    } else {
        return factorial(n - 1, n * a);
    }
}

Now, the recursive call appears in the tail position where it can be subject to tail-call optimization.

A crucial change here is the introduction of the additional argument a which "accumulates" the factorial. This removes the need to allocate a new stack frame as there is no final multiplication that needs to be done for each recursive call.

Tail-call optimization effectively makes tail-recursive functions a loop!

function factorial(n: number, a: number): number {
    let current_n = n;
    let current_a = a;

    // Uninitialized.
    let result;

    while (true) {
        if (current_n == 0 || current_1 == 1) {
            result = current_a;
            break;
        } else {
            current_n = current_n - 1;
            current_a = current_n * a;
        }
    }

    return result;
}

Complex Recursive Flow

While these optimizations are nice to have, they fall a little short once more complex control flow is introduced in recursive algorithms. To give a motivating example, I'll be defining a functional-style binary tree in TypeScript, as well as an accompanying map operation.

// Tagged unions

interface Tip<_T> {
    kind: "Tip",
}

interface Branch<T> {
    kind: "Branch",
    left: Tree<T>,
    value: T,
    right: Tree<T>,
}

type Tree<T> = Tip<T> | Branch<T>;

// Constructors

function tip<T>(): Tree<T> {
    return { kind: "Tip" };
}

function branch<T>(left: Tree<T>, value: T, right: Tree<T>): Tree<T> {
    return { kind: "Branch", left, value, right }
}

// Map

function map<T, U>(f: (value: T) => U, tree: Tree<T>): Tree<U> {
    switch (tree.kind) {
        case "Tip":
            return tip();
        case "Branch":
            let left = map(f, tree.left);
            let value = f(tree.value);
            let right = map(f, tree.right);
            return branch(left, value, right);
    }
}

I'd like to focus on the definition for map, specifically the "Branch" case:

case "Branch":
    let left = map(f, tree.left);
    let value = f(tree.value);
    let right = map(f, tree.right);
    return branch(left, value, right);

Notice how the recursive call is performed sequentially for both the left and right branches. However, neither call can be in the tail position to be optimized away by the compiler.

Mechanically transforming the map function to be tail-recursive is possible (and is a good homework activity), but that transformation is tedious and doesn't really scale well.

Hint: It involves defining an accumulator that represents the current state and what to do next.

There's another way to solve this dilemma that, in my opinion, is really elegant and ties everything I've talked about in this post very neatly. But before then, there's one last useful concept I'd like to talk about.

Continuation-Passing Style

At a high-level, continuation-passing style is a style of programming in which control is made explicit through continuations—in turn, continuations encapsulate information pertinent to the program's state, including whatever instructions need to be executed.

In TypeScript, continuation-passing style can be achieved by modeling continuations as functions that need to be called once a function finishes execution.

Note that other languages such as Scheme implement continuations as first-class, but I won't be talking about that in this post.

We can start by defining factorial in continuation-passing style:

function factorial<T>(n: number, k: (value: number) => T): T {
    if (n == 0 || n == 1) {
        return k(1);
    } else {
        return factorial(n - 1, (n_1) => {
            return k(n * n_1);
        });
    }
}

Aside from n, the continuation k is passed when calling the function. Usually, the identity function is passed as the default continuation:

console.log(factorial(10, (x) => x));

Notice how in the base case, instead of simply returning 1, we return the result of calling k with 1.

Meanwhile for the recursive case, we call factorial as usual. Aside from n - 1, a continuation that describes what to do with the result is also passed. In this case, that would be calling the curent continuation k to return n * n_1.

The biggest difference between the original and CPS definitions is how results are bound to names. In the original definition, the result is simply bound to a name for further use. On the other hand, the result is passed as an argument to the continuation in the CPS definition.

let n_1 = factorial(n - 1);
return n * n_1;

// in CPS

return factorial(n - 1, (n_1) => {
    return k(n * n_1);
});

One thing you may or may not have noticed is how function calls in the continuation-passing style definition appear in the tail-position!

We can see this in action with Bun, which just so happens to implement TCO through JavaScriptCore! Let's sprinkle various console.trace calls in our implementation:

function factorial(n: number, k: (value: number) => number): number {
    console.trace(`factorial(${n})`);
    if (n == 0 || n == 1) {
        return k(1);
    } else {
        return factorial(n - 1, (n_1) => {
            console.trace(`factorial(${n - 1}) = ${n_1}`);
            return k(n * n_1);
        });
    }
}

factorial(5, (x) => {
    console.trace(`identity(${x})`);
    return x;
});

This should yield the following result. Unlike in Node.js, the stack trace remains at a constant depth rather than growing in size!

factorial(5)
      at factorial (./index.ts:66:5)
      at ./index.ts:77:1
factorial(4)
      at factorial (./index.ts:66:5)
      at ./index.ts:77:1
factorial(3)
      at factorial (./index.ts:66:5)
      at ./index.ts:77:1
factorial(2)
      at factorial (./index.ts:66:5)
      at ./index.ts:77:1
factorial(1)
      at factorial (./index.ts:66:5)
      at ./index.ts:77:1
factorial(1) = 1
      at ./index.ts:71:13
      at ./index.ts:77:1
factorial(2) = 2
      at ./index.ts:71:13
      at ./index.ts:77:1
factorial(3) = 6
      at ./index.ts:71:13
      at ./index.ts:77:1
factorial(4) = 24
      at ./index.ts:71:13
      at ./index.ts:77:1
identity(120)
      at ./index.ts:78:5
      at ./index.ts:77:1

Reformulating to CPS

With some knowledge on how to define functions in the continuation-passing style, we can go back to our recursive map function such that it can be subject to tail-call optimization!

To recap, the original definition goes as follows:

function map<T, U>(f: (value: T) => U, tree: Tree<T>): Tree<U> {
    switch (tree.kind) {
        case "Tip":
            return tip();
        case "Branch":
            let left = map(f, tree.left);
            let value = f(tree.value);
            let right = map(f, tree.right);
            return branch(left, value, right);
    }
}

In continuation-passing style, it could look like:

function map_cps<T, U, K>(
    f: (value: T) => U,
    tree: Tree<T>,
    k: (result: Tree<U>) => K
): K {
    switch (tree.kind) {
        case "Tip":
            return k(tip());
        case "Branch":
            return map_cps(f, tree.left, (left) => {
                let value = f(tree.value);
                return map_cps(f, tree.right, (right) => {
                    return k(branch(left, value, right));
                });
            });
    }
}

Like with the factorial function, the results from the recursive calls are bound as arguments to continuations rather than local variables in the current stack frame.

One thing to note here is that not all function calls are in continuation-passing style, and not everything needs to be, just the ones that have the potential to blow up the call stack. It would be a good exercise to do so, though!

We can determine this function's stack safety with the following test:

let tree = tip<number>();
for (let i = 0; i < 1_000_000; i++) {
    tree = branch<number>(tree, 42, tip());
}

let mapped_tree = map_cps((x) => x * 2, tree, (x) => x);
console.log(mapped_tree);

With Bun, it finishes execution!

$ bun run index.ts
{
  kind: "Branch",
  left: {
    kind: "Branch",
    left: {
      kind: "Branch",
      left: [Object ...],
      value: 84,
      right: [Object ...],
    },
    value: 84,
    right: {
      kind: "Tip",
    },
  },
  value: 84,
  right: {
    kind: "Tip",
  },
}

Meanwhile in Node.js, we get the dreaded:

var map_cps = function(f, tree, k) {
                      ^

RangeError: Maximum call stack size exceeded
    at map_cps (file:///./index.js:8:23)
    at map_cps (file:///./index.js:13:14)
    at map_cps (file:///./index.js:13:14)
    at map_cps (file:///./index.js:13:14)
    at map_cps (file:///./index.js:13:14)
    at map_cps (file:///./index.js:13:14)
    at map_cps (file:///./index.js:13:14)
    at map_cps (file:///./index.js:13:14)
    at map_cps (file:///./index.js:13:14)
    at map_cps (file:///./index.js:13:14)

Node.js v21.6.0

Tradeoffs and Thoughts

Like with most alternative approaches in programming, defining functions in terms of continuation-passing style has its own tradeoffs.

In particular, continuation-passing style in JavaScript involves allocating heap memory for the continuation functions. Heap memory is often traded for stack safety in these instances. Thankfully, we're not in the early days of tech anymore and memory is cheap now.

Likewise, continuation-passing style works best in languages that have first-class functions, and may not necessarily translate to languages patterned after C. While possible, it may be tedious to define an abstraction so it's not worth it for most problems.

Speaking of, there might be instances where you'll find yourself looking for stack-safety through CPS even though the algorithms you're looking to use it for don't unreasonably grow the call stack.

For example, it's reasonable to assume that AST traversals don't really need stack safety, since whatever data they're going to be traversing is bounded reasonably. If they do cause a stack overflow, then it's more likely to be a data problem rather than a stack safety problem.

Recursion is… Fine

Hopefully, the concepts that I talked about in this blog post made it clear that recursion is not an irredeemably evil programing construct.

It's able to flash its elegance without sacrificing performance just with the help of an optimizing compiler or language runtime, to which there have been plenty of in the history of computer science.

The topic of iteration versus recursion has a lot of nuance that is ultimately based on the context in which the two features are being talked about. I hope this blog post made you curious about that!

I highly recommend getting into language development to gain a holistic understanding of how systems like these interact with each other.