Avoiding Stack Overflows with Trampoline Functions

Teaching recursion revealed that seemingly simple problems could harbor surprisingly elegant and optimized solutions. This led me to experiment by asking different LLMs some of these questions. Most initially overlooked the most efficient approaches, only finding them when explicitly asked. However, one LLM stood out: it recommended using a trampoline function to mitigate stack overflow risks – a technique I didn’t know. That unexpected insight sparked the exploration that follows.

Recursion is a powerful programming technique where a function calls itself to solve smaller instances of the same problem. However, deep recursion can lead to a common issue: the “Maximum call stack size exceeded” error, or stack overflow. Let’s explore this with an example and see how trampoline functions can help us overcome this limitation in environments like Node.js and Deno.

A Simple Recursive Function

Consider a function that prints all even numbers within a given range:

1
function printEvenNumbers(start: number = 0, end: number = 100): void {
2
  // Base case: stop when start exceeds end
3
  if (start > end) {
4
    return;
5
  }
6

7
  // Print if the number is even
8
  if (start % 2 === 0) {
9
    console.log(start);
10
  }
11

12
  // Recursive call for the next number
13
  printEvenNumbers(start + 1, end);
14
}
15

16
// Usage:
17
printEvenNumbers();
18
// Output: 0, 2, 4, ..., 100

This function works well for small ranges.

The Stack Overflow Problem

Each time printEvenNumbers calls itself, a new frame is added to the call stack. This frame stores information about the function call, like its parameters and local variables. If the range (and thus the recursion depth) is very large, the call stack can run out of space, leading to a stack overflow error.

Theoretical Solution: Tail Call Optimization (TCO)

Tail Call Optimization (TCO) is a feature where a compiler or interpreter can optimize certain types of recursive calls, known as “tail calls”. A tail call occurs when a function’s very last action is to call itself (or another function) and return its result immediately. With TCO, the engine can reuse the current stack frame instead of creating a new one, effectively turning recursion into iteration under the hood and preventing stack overflows.

We can try to make our function tail-recursive:

1
function printEvenNumbersTCO(start: number = 0, end: number = 100): void {
2
  if (start > end) {
3
    return;
4
  }
5

6
  if (start % 2 === 0) {
7
    console.log(start);
8
  }
9

10
  // This is now a tail call
11
  return printEvenNumbersTCO(start + 1, end);
12
}
13

14
// Usage:
15
// printEvenNumbersTCO(0, 100000); // Might still cause stack overflow!

We can even make it more efficient by only processing even numbers:

1
function printEvenNumbersTCOOptimized(start: number = 0, end: number = 100): void {
2
  if (start > end) {
3
    return;
4
  }
5

6
  // start is guaranteed to be even (or the first odd number if initial start was odd)
7
  if (start % 2 === 0) {
8
     console.log(start);
9
     // Tail call jumping by 2
10
     return printEvenNumbersTCOOptimized(start + 2, end);
11
  } else {
12
     // Adjust if starting odd, then jump by 2
13
     console.log(start + 1); // Print the next even number
14
     return printEvenNumbersTCOOptimized(start + 3, end);
15
  }
16
}
17

18
// Start with an even number for simplicity:
19
// printEvenNumbersTCOOptimized(0, 100000); // Might still cause stack overflow!

The Catch: While TCO is a great concept, most JavaScript environments (including Node.js, Deno, and major browsers except Safari) do not implement Tail Call Optimization. This means that even if your code is written in a tail-recursive style, you’ll still encounter stack overflows with deep recursion in these environments.

Practical Solution: Trampoline Functions

Since we can’t rely on TCO, we need another way to handle deep recursion. This is where the trampoline pattern comes in. Instead of making a direct recursive call, our function will return a thunk—a zero-argument function that, when called, performs the next step of the computation. A central “trampoline” function then repeatedly calls these thunks until a final result (not a thunk) is returned.

This turns recursion into iteration, keeping the stack flat.

Here’s how we implement it:

1. The Generic Trampoline Function:

1
// Type for the thunk or the final result
2
type TrampolineResult<T> = T | (() => TrampolineResult<T>);
3

4
// The trampoline function itself
5
function trampoline<T>(firstThunk: () => TrampolineResult<T>): T {
6
  let currentThunk = firstThunk;
7

8
  // Keep executing thunks as long as a function is returned
9
  while (typeof currentThunk === 'function') {
10
    currentThunk = currentThunk() as (() => TrampolineResult<T>);
11
  }
12

13
  // When a non-function value is returned, it's the final result
14
  return currentThunk as T;
15
}

2. Modify the Recursive Function to Return Thunks:

We adapt our printEvenNumbers logic to return either void (in the base case) or a thunk representing the next step.

1
function printEvenNumbersThunk(start: number = 0, end: number = 100): TrampolineResult<void> {
2
  // Base case: Return the final result (void)
3
  if (start > end) {
4
    return undefined; // Or simply return;
5
  }
6

7
  if (start % 2 === 0) {
8
    console.log(start);
9
  }
10

11
  // Return a thunk for the next step
12
  return () => printEvenNumbersThunk(start + 1, end);
13
}

3. Combine and Run:

We use the trampoline function to execute our thunk-returning function.

1
// Start the process by calling the trampoline with the initial thunk
2
trampoline(() => printEvenNumbersThunk(0, 100));
3
// Output: 0, 2, 4, ..., 100
4

5
// Now, even with a large range, it won't overflow the stack:
6
// trampoline(() => printEvenNumbersThunk(0, 100000)); // Works!

4. More Efficient Trampoline Version:

We can apply the optimization of skipping odd numbers to the trampoline version as well:

1
function printEvenNumbersThunkOptimized(start: number, end: number): TrampolineResult<void> {
2
 // Base case
3
  if (start > end) {
4
    return undefined;
5
  }
6

7
  // Ensure start is even (only needs check on first call if starting potentially odd)
8
  // This simple version assumes start is initially even.
9
  console.log(start);
10

11
  // Return a thunk that jumps by 2
12
  return () => printEvenNumbersThunkOptimized(start + 2, end);
13
}
14

15
// Make sure the initial call starts even if needed
16
const initialStart = 0;
17
const initialEnd = 100;
18
const firstStart = initialStart % 2 === 0 ? initialStart : initialStart + 1;
19

20
// Run the optimized version
21
// trampoline(() => printEvenNumbersThunkOptimized(firstStart, initialEnd)); // Works!

Conclusion

While recursive functions offer elegance, they risk stack overflows in JavaScript environments lacking TCO. Tail-recursive style alone doesn’t prevent this issue in Node.js or Deno. The trampoline pattern provides a practical (mind-bending) solution by transforming deep recursion into iteration, allowing you to leverage a recursive programming style without blowing the stack.

Clever.