tailstep

tailstep

Simple trampoline-based tail recursion for modern JavaScript/TypeScript

About

Tail recursion is a technique that enables recursive functions to be optimized into loops, preventing stack overflow in many programming languages. However, JavaScript does not natively support tail call optimization (TCO). This library offers a simple way to implement tail-recursive functions in JavaScript/TypeScript.

Installation

npm install tailstep

Usage

Consider how we can implement a factorial function using tail recursion in simple JavaScript:

function factorial(n, acc = 1) {
  if (n === 0) return acc;
  return factorial(n - 1, n * acc);
}

However, this implementation will cause a stack overflow when n is large enough. To prevent this, we can use the tailRec function provided by this library:

import { done, step, tailRec } from "tailstep";

const factorial = tailRec((n, acc = 1) => {
  if (n === 0) return done(acc);
  return step(n - 1, n * acc);
});

Here, done is used to return the final result, while step signals that the recursion should continue with the given arguments. The tailRec function automatically converts the tail-recursive function into a loop.

For TypeScript users, simply add type annotations to the function arguments:

import { done, step, tailRec } from "tailstep";

const factorial = tailRec((n: number, acc: number = 1) => {
  //  ^?: (n: number, acc?: number) => number
  if (n === 0) return done(acc);
  return step(n - 1, n * acc);
});

For easier debugging, consider using a named function instead of an arrow function. This ensures that the function name will appear in the stack trace:

const factorial = tailRec(function factorial(n, acc = 1) {
  if (n === 0) return done(acc);
  return step(n - 1, n * acc);
});

The tailRec function may not work well with TypeScript when defining functions with generic types. In such cases, you may prefer to use the traditional trampoline approach:

import { done, cont, bounce, type Bounce } from "tailstep";

function factorial(n: number): number {
  function loop(acc: number, n: number): Bounce<number> {
    if (n === 0) return done(acc);
    return cont(() => loop(n * acc, n - 1));
  }
  return bounce(loop(1, n));
}

Here’s how these functions are implemented in the library if you’re curious:

const done = (value) => ({ _tag: "done", value });
const cont = (thunk) => ({ _tag: "cont", thunk });

function bounce(bounce) {
  let current = bounce;
  while (current._tag === "cont") current = current.thunk();
  return current.value;
}

const step = (...args) => ({ _tag: "stepSignal", args });

function tailRec(f) {
  const fn = (...args) => {
    let current = f(...args);
    while (current._tag === "stepSignal") current = f(...current.args);
    return current.value;
  };
  return Object.defineProperty(fn, "name", { value: f.name });
}