Trampolining
Stack-safe recursion.
Trampolining is a free Scala for Backend Engineering & Functional Programming lesson on CoddyKit — lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Scala for Backend Engineering & Functional Programming learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
The Limit of @tailrec
@tailrec only optimizes a function calling itself directly. It cannot help with mutual recursion (two functions calling each other), which still grows the stack. Trampolining solves this.
The Mutual Recursion Problem
Consider isEven and isOdd defined in terms of each other. For a large number this overflows the stack, and neither can be marked @tailrec.
object Main {
def isEven(n: Int): Boolean = if (n == 0) true else isOdd(n - 1)
def isOdd(n: Int): Boolean = if (n == 0) false else isEven(n - 1)
def main(args: Array[String]): Unit = {
println(isEven(10))
}
}What is a Trampoline?
A trampoline turns recursive calls into data. Instead of calling itself, a function returns a description of the next step. A driver loop repeatedly runs these steps, keeping the stack flat.
TailRec in the Standard Library
Scala provides scala.util.control.TailCalls with the TailRec type. Use done(x) for a final result and tailcall(...) to defer the next call.
import scala.util.control.TailCalls._
object Main {
def isEven(n: Int): TailRec[Boolean] =
if (n == 0) done(true) else tailcall(isOdd(n - 1))
def isOdd(n: Int): TailRec[Boolean] =
if (n == 0) done(false) else tailcall(isEven(n - 1))
def main(args: Array[String]): Unit = {
println(isEven(100000).result)
}
}done and tailcall
The two building blocks:
done(value)wraps a final answer.tailcall(expr)defers a call that returns aTailRec.
Calling .result runs the trampoline loop and produces the value.
Stack Safety
Because each tailcall returns control to the driver loop instead of nesting a Java call, the JVM stack never grows with the recursion depth. The example above handles 100,000 steps without overflow.
Trampolining Self-Recursion
Trampolines also work for ordinary deep self-recursion when you cannot easily use an accumulator. Here a deep countdown stays stack-safe.
import scala.util.control.TailCalls._
object Main {
def countDown(n: Int): TailRec[Int] =
if (n == 0) done(0) else tailcall(countDown(n - 1))
def main(args: Array[String]): Unit = {
println(countDown(500000).result)
}
}Combining Results with flatMap
TailRec supports map and flatMap, so you can do work after a deferred call while staying stack-safe.
import scala.util.control.TailCalls._
object Main {
def sum(n: Int): TailRec[Int] =
if (n == 0) done(0)
else tailcall(sum(n - 1)).map(_ + n)
def main(args: Array[String]): Unit = {
println(sum(100000).result)
}
}How the Driver Loop Works
Conceptually, .result runs a loop: take the current step; if it is done, return its value; if it is a deferred call, evaluate one layer and continue. All in constant stack space.
Trampolining in Effect Libraries
Libraries like Cats Effect and ZIO trampoline their flatMap chains internally, which is why you can build deeply nested effect programs without stack overflow. Trampolining is the foundation of stack-safe functional effects.
When to Trampoline
Use a trampoline when:
- You have mutual recursion that cannot be a single tail-recursive function.
- The recursion is too deep for the stack and an accumulator does not fit.
For simple self-recursion, prefer @tailrec with an accumulator first.
Quick Check
Test your understanding of trampolining.
Recap
You learned trampolining:
- It makes mutual and very deep recursion stack-safe.
- Use
TailCalls:done(x)andtailcall(...), then.result. TailRecsupportsmap/flatMap.- It underpins stack-safe effect libraries.
Frequently asked questions
Is the “Trampolining” lesson free?
Yes — the full text of “Trampolining” is free to read here on the web, and the Scala for Backend Engineering & Functional Programming course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Scala for Backend Engineering & Functional Programming course, upgrade to CoddyKit PRO.
What will I learn in “Trampolining”?
Stack-safe recursion. You practise Scala for Backend Engineering & Functional Programming with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Scala for Backend Engineering & Functional Programming?
No prior experience is required. Scala for Backend Engineering & Functional Programming on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Trampolining” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Scala for Backend Engineering & Functional Programming lesson?
Yes. Every Scala for Backend Engineering & Functional Programming lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.