Understanding Trampolining in Cats Effect: A Deep Dive into Stack-Safe Recursion

Or: How I Learned to Stop Worrying and Love the Heap

Trampolining is one of those elegant computer science techniques that solves a fundamental problem in functional programming. When you chain operations together using flatMap, each call traditionally adds a frame to the call stack. Eventually, with enough operations, you run out of stack space and your program crashes with a StackOverflowError. This is where trampolining comes in, providing a way to achieve stack-safe recursion by converting recursive calls into a data structure that can be interpreted iteratively.

Understanding trampolining is essential for working with Cats Effect and similar effect systems. It’s the foundation that allows you to safely chain thousands or even millions of IO operations without worrying about stack overflow. In this article, I am going to explore how trampolining works, build a complete implementation from scratch, and connect it to how Cats Effect’s IO monad achieves stack safety. All code in this article is available from my Github repository.

The Stack Overflow Problem

To understand why trampolining is necessary, we first need to see the problem it solves. Consider a simple countdown function implemented naively. The implementation creates a new computation that runs the previous effect, passes the result to a continuation function, and then runs that result. This creates nested function calls on the stack. The following example demonstrates the issue.

class NaiveIO[+A](private val effect: () => A):
  def flatMap[B](f: A => NaiveIO[B]): NaiveIO[B] =
    new NaiveIO(() => f(effect()).run())
  
  def run(): A = effect()

object NaiveIO:
  def pure[A](value: A): NaiveIO[A] = 
    new NaiveIO(() => value)

def naiveCountdown(n: Int): NaiveIO[Int] =
  if n <= 0 then NaiveIO.pure(0)
  else NaiveIO.pure(n).flatMap(_ => naiveCountdown(n - 1))

This works fine for small numbers. You can call naiveCountdown(10) without problems. However, trying to call naiveCountdown(100000) will cause a StackOverflowError. Each flatMap call creates a new function that runs the previous effect, and these calls nest deeper and deeper on the call stack.

When you execute countdown(3), the execution proceeds through several steps. First, it evaluates pure(3).flatMap(f), which creates a new function. When that function runs, it needs to evaluate countdown(2), which evaluates pure(2).flatMap(f), creating another function. This continues until countdown(0), with each step adding a frame to the call stack. The stack depth equals the recursion depth, which is why deep recursions fail.

The problem becomes clearer when we visualize what’s happening. The naive approach uses the stack to track each recursive call. You get a chain of stack frames where countdown(3) calls countdown(2), which calls countdown(1), which calls countdown(0). Each arrow represents a stack frame, and the depth grows linearly with the input. This is fundamentally limited by the JVM’s stack size, which is typically a few megabytes.

Here’s a detailed step-by-step execution trace for naiveCountdown(3).run():

Step 1: Call naiveCountdown(3)

naiveCountdown(3)
// n = 3, not <= 0, so else branch

Step 2: Create pure(3)

NaiveIO.pure(3)
// Returns: NaiveIO(effect = () => 3)

Step 3: Call flatMap

NaiveIO(effect = () => 3).flatMap(_ => naiveCountdown(2))
// Creates: new NaiveIO(() => f(effect()).run())
// Where:
//   f = (_ => naiveCountdown(2))
//   effect = (() => 3)
// Expands to: new NaiveIO(() => naiveCountdown(2).run())

Result of naiveCountdown(3):

NaiveIO(effect = () => naiveCountdown(2).run())

Notice: naiveCountdown(2) hasn’t been called yet! We just stored a reference to it in a lambda.

Step 4: Call naiveCountdown(3).run()

NaiveIO(effect = () => naiveCountdown(2).run()).run()
// run() executes: effect()
// Which calls: naiveCountdown(2).run()

[Stack Frame 1: naiveCountdown(3).run()]

Step 5: Inside naiveCountdown(2).run()

// First, naiveCountdown(2) constructs:
naiveCountdown(2)
// Returns: NaiveIO(effect = () => naiveCountdown(1).run())

// Then .run() is called:
NaiveIO(effect = () => naiveCountdown(1).run()).run()
// run() executes: effect()
// Which calls: naiveCountdown(1).run()

[Stack Frame 1: naiveCountdown(3).run()]
[Stack Frame 2: naiveCountdown(2).run()]

Step 6: Inside naiveCountdown(1).run()

// First, naiveCountdown(1) constructs:
naiveCountdown(1)
// Returns: NaiveIO(effect = () => naiveCountdown(0).run())

// Then .run() is called:
NaiveIO(effect = () => naiveCountdown(0).run()).run()
// run() executes: effect()
// Which calls: naiveCountdown(0).run()

[Stack Frame 1: naiveCountdown(3).run()]
[Stack Frame 2: naiveCountdown(2).run()]
[Stack Frame 3: naiveCountdown(1).run()]

Step 7: Inside naiveCountdown(0).run()

// First, naiveCountdown(0) constructs:
naiveCountdown(0)
// n = 0, so if branch
// Returns: NaiveIO.pure(0) = NaiveIO(effect = () => 0)

// Then .run() is called:
NaiveIO(effect = () => 0).run()
// run() executes: effect()
// Which calls: (() => 0)()
// Returns: 0

[Stack Frame 1: naiveCountdown(3).run()]
[Stack Frame 2: naiveCountdown(2).run()]
[Stack Frame 3: naiveCountdown(1).run()]
[Stack Frame 4: naiveCountdown(0).run()] ← returns 0

Step 8: Unwinding the stack

// Stack Frame 4 returns 0 to Frame 3
[Stack Frame 3: naiveCountdown(1).run()] ← returns 0

// Stack Frame 3 returns 0 to Frame 2
[Stack Frame 2: naiveCountdown(2).run()] ← returns 0

// Stack Frame 2 returns 0 to Frame 1
[Stack Frame 1: naiveCountdown(3).run()] ← returns 0

// Final result: 0

Call:     naiveCountdown(3).run()
          ↓
Expands:  (() => naiveCountdown(2).run())()
          ↓
          naiveCountdown(2).run()
          ↓
Expands:  (() => naiveCountdown(1).run())()
          ↓
          naiveCountdown(1).run()
          ↓
Expands:  (() => naiveCountdown(0).run())()
          ↓
          naiveCountdown(0).run()
          ↓
Expands:  (() => 0)()
          ↓
Returns:  0

The critical issue is that each run() call creates a new stack frame that waits for the nested run() to complete:

naiveCountdown(3).run()          [Frame 1 - WAITING]
  └─> naiveCountdown(2).run()    [Frame 2 - WAITING]
      └─> naiveCountdown(1).run() [Frame 3 - WAITING]
          └─> naiveCountdown(0).run() [Frame 4 - EXECUTING]
              └─> returns 0

With naiveCountdown(100000), you’d have 100,000 stack frames waiting, which exceeds the JVM’s stack size limit.

Key Insight

The flatMap creates a nested function structure: () => f(effect()).run()
When run() is called, it must do the following.

1. Call effect() to get a value

2. Pass that value to f to get a new NaiveIO

3. Call run() on that new NaiveIO

Step 3 is not in tail position because it happens inside the lambda that was stored in effect. This creates the nested stack frames that lead to overflow.

Converting Execution into Data

The key insight behind trampolining is to represent computations as data structures rather than executing them immediately. Instead of running operations as we encounter them, we build a description of what to do, stored as objects in heap memory. Then we can interpret this description iteratively without growing the stack.

Consider the difference between these two approaches. In the naive approach, recursion happens during execution. Each call adds to the stack, and the stack depth equals the recursion depth. In the data approach, recursion happens during data construction. We create objects on the heap, the stack depth remains constant at O(1) during construction, and we can interpret the tree structure iteratively.