skip to content

What does the compiler actually generate for a `tailrec` function, and what are the engineering trade-offs of using it versus a hand-written loop?

level: principalimportance: nice to knowfreq 22%

answer

  1. Generates while(true) + reassign locals + backward goto
  2. No frame per call -> O(1) stack, loop-speed
  3. Zero-cost abstraction: same as hand-written loop
  4. Warning-only safety net -> allWarningsAsErrors on hot paths
  5. Mutual recursion / non-tail -> trampoline (thunks)

basics

~10 s

The compiler turns the recursion into a plain while(true) loop that updates the parameters and jumps back. So at runtime it's the same as a hand-written loop — you just get cleaner, recursive-looking source.

solid answer

~50 s

For a `tailrec` function the Kotlin compiler emits an **iterative loop**: parameters become mutable local variables, the body becomes a `while (true)` body, each tail call reassigns those locals to the new argument values and jumps back to the top, and the base case `return`s. There is **no recursion in the bytecode** and no per-call frame, so it runs in constant stack space with the same performance characteristics as a manual loop — essentially zero runtime overhead. The trade-off is mostly about **readability and safety**: `tailrec` lets you express an inherently iterative algorithm in clear recursive form while guaranteeing (via the compiler warning) that it won't blow the stack. Risks: the optimization silently degrades to plain recursion if you accidentally break tail position (warning-only), so it should be paired with treating that warning as an error; and it can't express mutual recursion, where you'd reach for a trampoline. It's a great fit for fixed-point iteration, accumulator folds, and walking linked structures.

code

kotlin · 3 lines
kotlin
tailrec fun gcd(a: Int, b: Int): Int =
    if (b == 0) a else gcd(b, a % b)
// compiles to a while(true) loop, O(1) stack

go deeper

for a junior

Understands tailrec avoids stack overflow but may not describe the generated loop.

for a middle

Can state it compiles to a loop and runs in constant stack space.

for a senior

Explains the simultaneous-reassignment loop, zero-cost framing, and the warning-only risk.

for a principal

Weighs readability/safety trade-offs, configures warnings-as-errors on hot paths, and reaches for trampolines where tailrec cannot apply.

## What the compiler generates Given: ```kotlin tailrec fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b) ``` the compiler produces bytecode equivalent to: ```kotlin fun gcd(a: Int, b: Int): Int { var a1 = a var b1 = b while (true) { if (b1 == 0) return a1 val newA = b1 val newB = a1 % b1 a1 = newA b1 = newB // implicit jump back to the top of the loop } } ``` Key points: - Parameters become **mutable locals** (`a1`, `b1`). - The recursive tail call becomes **simultaneous reassignment** of those locals followed by a backward jump (`goto` at the bytecode level) — note the temporaries (`newA`/`newB`) so arguments are computed against the old values before assignment. - The base case becomes a `return`. - **No method invocation, no new frame** per iteration. ## Runtime characteristics - **Stack:** O(1) — one frame total, vs O(n) for naive recursion. - **Speed:** equivalent to a hand-written loop; the JIT sees ordinary loop bytecode. No call overhead, no megamorphic dispatch. - **Allocation:** none beyond what the body already does. So `tailrec` is a **zero-cost abstraction** in the runtime sense. ## Engineering trade-offs vs. a manual loop **For `tailrec`:** - Source stays **declarative and recursive**, often matching the mathematical definition (gcd, fixed-point, list traversal) more readably than mutable loop state. - The compiler **proves** tail position; you get a warning if you break it — a safety net a hand loop doesn't need but a naive recursion lacks. - Immutable-style code (no `var`s in your source) is easier to reason about. **Against / cautions:** - The safety net is **warning-only**. A refactor that adds work after the call silently reverts to stack-hungry recursion. Mitigate by configuring the build to treat that warning as an error (e.g. `allWarningsAsErrors`) for hot paths. - **No mutual recursion** — for state machines bouncing between functions, use a **trampoline**: each step returns a thunk (`() -> T` or a sealed `More/Done`) and a driver loop invokes them, keeping the stack flat. - For trivial loops, plain `for`/`while` may be more idiomatic to teammates; reserve `tailrec` where the recursive shape genuinely aids clarity. ## When to reach for it - Accumulator folds, fixed-point iteration (`repeat until stable`), Euclid's algorithm, walking a singly-linked list/AST spine, retry-with-backoff state. ## Trampoline sketch (the escape hatch) ```kotlin sealed interface Bounce<out T> data class Done<T>(val value: T) : Bounce<T> data class More<T>(val next: () -> Bounce<T>) : Bounce<T> fun <T> run(start: Bounce<T>): T { var b = start while (b is More) b = b.next() return (b as Done).value } ``` This covers cases `tailrec` cannot, at the cost of allocating thunks.

  • How would you make the warning a hard failure for a critical tailrec function?
    Enable `allWarningsAsErrors` (or the relevant compiler flag) so the 'not a tail call' / 'no tail calls found' warning fails the build.
  • What is a trampoline and when do you use it over tailrec?
    A loop that repeatedly invokes returned thunks (Done/More) instead of recursing; use it for mutual recursion or non-tail recursion that tailrec can't optimize.

It's a compiler-checked promise: write the recursion, get the loop, and a warning bell if you ever break the promise.

saying these in an interview costs you the question

  • Claiming `tailrec` adds runtime overhead compared to a loop
  • Not knowing it compiles to a while loop with reassigned locals
  • Ignoring that the safety net is warning-only
  • Unaware of trampolining as the alternative for mutual recursion

context

resolving links…