Kotlin's DeepRecursiveFunction turns deep recursion into a heap-allocated trampoline while keeping direct-style code, built on suspend functions. This post explains why that works, then builds a Scala 3 macro that does the same trick with no coroutines and no Project Loom, by rewriting a recursive method into a TailRec state machine at compile time.
The Stack Runs Out
Can we get direct-style, stack-safe deep recursion in Scala with no monads, no coroutines, no virtual threads, no effect algebra? To a point, yes. Let's start from the beginning, with the most ordinary recursive function there is:
sum(1_000) works fine but sum(1_000_000) fails with a StackOverflowError and @tailrec won't save it, either (the recursive call isn't in tail position). 1 + sum(n - 1) has to return from sum before the 1 + can happen, so every call needs a stack frame to come back to.
The standard fix is an accumulator, moving the running total into a parameter so the recursive call becomes the entire return value instead of part of an expression:
sumAcc(1_000_000) runs fine now. It works because the accumulator carries sum's running total forward one call at a time, but such a solution doesn't scale. Take tree depth as an example: max(depth(left), depth(right)). Here, left and right are separate subtrees rather than sequential steps, so a single accumulator cannot carry both branches forward at the same time. That is the core challenge: we want to keep the clean, intuitive recursive structure (arbitrary branching included) while eliminating the JVM stack frames that cause overflows. To solve this, we will first look at how Scala traditionally handles this by manually offloading execution from the call stack to heap memory through a technique called trampolining. Then, we will explore how Kotlin avoids this manual rewrite altogether, and finally build a Scala 3 macro that gives us the best of both worlds.
Trampolines, the Manual Way
Scala's standard library ships an escape hatch for exactly this: scala.util.control.TailCalls. We give up direct recursion and hand-build a trampoline instead, a value that says "call this next" instead of calling it:
done and tailcall build a TailRec[A], a tiny free monad over three cases: Done, Call, Cont. .result drives the computation to completion with a loop that's itself annotated @tailrec, so the whole computation runs on one JVM stack frame no matter how deep the "recursion" goes. It's the textbook trampoline from "Stackless Scala with Free Monads", and it's what Cats Effect's IO, Monix's Task and ZIO's runtime all do under the hood too. Trampolining is baked into their run loops, which is exactly why stack-unsafe recursion inside flatMap chains isn't a problem for them.
The price is the same everywhere, though: the code stops looking like the function it computes. Even the library's own scaladoc example for two-call recursion shows the tax:
Every self-call gets wrapped in tailcall, every use of its result moves into a flatMap, and the return type stops being Int.
The Kotlin Approach
Kotlin's standard library has DeepRecursiveFunction, and it does something that looks like it shouldn't be possible: the same stack safety, with none of the rewriting. Swap depth(...) for callRecursive(...), wrap the body in DeepRecursiveFunction { }, and a function that would blow the stack doesn't. The shape of the code doesn't change: if, +, ordinary calls, no monad, no flatMap. It reads exactly like fib:
The docs give away the mechanism in one line: it "keeps its stack on the heap." And the block parameter's type tells us how: suspend DeepRecursiveScope<T, R>.(T) -> R. It's a coroutine.
Why It Actually Works
suspend is an instruction to the Kotlin compiler: rewrite this function body into continuation-passing style. Every suspension point becomes a state in a compiler-generated state machine, and each state's local variables get hoisted into a heap-allocated object instead of living on the JVM stack. That is standard coroutine machinery: it lets execution pause and release its thread without losing the function's internal state.
DeepRecursiveFunction takes that same machinery and drives it by hand rather than relying on a dispatcher. Roman Elizarov explains the details in his article on deep recursion with coroutines, but the key takeaway is straight to the point: a compiler-driven CPS transform (suspend) paired with a tight driver loop that turns "call and wait" into simple field mutations. The call stack becomes a chain of heap objects, evaluated by one method that stays within a fixed JVM stack frame.
Can Scala Steal This?
Scala 3 has no suspend, and no built-in mechanism for rewriting an arbitrary function body into a state machine. And reaching for Project Loom or virtual threads wouldn't fix this. It's JVM 21+ only, and by design it doesn't buy the extra depth we'd want. JEP 444 is explicit that a virtual thread's heap-allocated stacks "grow and shrink as the application runs, both to be memory-efficient and to accommodate stacks of depth up to the JVM's configured platform thread stack size". That is up to the same depth an ordinary thread already gets, not past it, and under G1 it can overflow earlier, at half a GC region, which can be as small as 512KB. A virtual thread moves the same fixed-depth stack onto the heap; it doesn't remove the one frame per call that's the actual problem.
But Scala 3 has something Kotlin's approach doesn't need and doesn't have: macros that see a method's AST at compile time. If the Kotlin compiler can mechanically turn a suspend lambda into a state machine, a macro can mechanically turn a self-recursive method's body into the TailRec-driven one, so the caller keeps writing direct-style recursion, and the trampoline gets generated. The target API looks like this:
We want to have it rewritten to the trampolined form automatically, like this:
Let's build it, one capability at a time.
Step 1: One Call, Nothing Fancy
Smallest useful target first: a call that is the whole branch, nothing wrapped around it:
Symbol.spliceOwner is the definition the macro is being expanded inside of. Since deepRecursive is the entire body of deepCountDown, that's deepCountDown itself, so .owner steps one level out to whatever encloses it. Everything the macro needs about deepCountDown comes straight off that symbol: methSymbol.paramSymss is the parameter symbols themselves, and param.termRef.widen recovers n's type from its own reference. The return type needs no lookup at all: T is already sitting there, inferred from body: Expr[T] at the call site, and since deepRecursive sits in deepCountDown's whole-body position, T is deepCountDown's return type.
Symbol.newMethod + MethodType synthesizes a sibling method with the same parameter and a TailRec[T] return type instead of T. Its name comes from Symbol.freshName("loop"), not the literal string. The actual generated method is called something like loop$macro$1, unique per expansion, so two deepRecursive calls in the same file never collide even before the JVM gets a chance to mangle local-method names on its own. Every example from here on calls it loop for readability; the real name is longer but never matters, since nothing in the macro ever looks it up by name, every reference is a direct Symbol handle. transform walks the body: If recurses into both branches, Inlined peels through and keeps going (more on that below), a self-call becomes tailcall(loop(...)), and anything else is a base case, wrapped in done.
Inlined is crucial, because without it, deepCountDown recurses forever, alternating between deepCountDown and loop. body: T is bound from an inline body: T parameter, and an inlined macro argument arrives already wrapped in an Inlined node. Without a case for it, that wrapper doesn't match If, so transform falls into case other, wraps the entire untransformed body, recursive call included, in a single done(...), and that done(...) evaluates the original expression eagerly. deepCountDown calls loop, loop calls deepCountDown right back. The trampoline is a no-op, and the bug stays silent until we run it deep enough to overflow.
Failing to rename parameters leads to a subtle bug. loop's parameter is a brand-new symbol, not deepCountDown's, so without renameParams, every n inside the body still points at the original parameter, which loop closes over instead of reading its own argument. The code type-checks, deepCountDown(5) compiles and runs, but never returns, because n never changes and the base case never fires.
With both fixes in, deepCountDown(1_000_000) returns 0 instead of blowing the stack. Progress, but only for the narrowest shape of recursion there is.
Step 2: A Call Buried Inside an Expression
Functions such as deepSum cannot be transformed:
The else branch is 1 + deepSum(n - 1) which, under the hood, is also an Apply node, since + is a method call. case Apply(fun, args) if fun.symbol == methSymbol no longer matches it: fun.symbol here is Int.+, not deepSum. Pattern-matching the leaf itself against "is this the call" doesn't scale: the leaf needs to be searched for a call buried anywhere inside it, and whatever's found needs to be trampolined and its eventual result spliced back into the original shape.
The expected outcome looks like this:
In our implementation, that's three new pieces. A search over the tree:
A substitution that swaps specific call nodes for their eventual results:
Matching is by reference (eq), not structural equality, because two syntactically identical recursive calls at different positions in the same expression are two distinct occurrences, and only one of them should be replaced by any given substitution.
And the leaf handler that ties them together, folding a chain of tailcall(...).flatMap { x => ... } over however many calls it found:
transform shrinks to two structural cases plus a fallback:
deepSum(1_000_000) now returns 1000000. Notice that nothing in our implementation restricts us to a single recursive call: buildChain folds over a List[Apply] of whatever length selfCallCollector found. Point the exact same macro at Fibonacci and Tribonacci, with two and three self-calls per branch respectively:
deepFib should expand to:
That's buildChain made visible: the first call's result is bound as x, the second call runs after it (each flatMap is a real dependency, not parallelism), bound as x₂, and only once both are in hand does replaceSubtrees splice them back into x + x₂, the original expression shape, with calls swapped for their bound results.
Step 3: More Shapes of Control Flow
transform currently understands exactly two structural forms: If and Inlined. Two more come up immediately in practice: a match, and a block with a local val before the tail expression:
Both are "keep walking until we hit a leaf, then stop" cases, same as If:
Match only transforms each case's right-hand side (a guard is a condition, not a value the function returns, so it's copied through untouched). Block transforms only its trailing expression; the local val prev = n - 1 stays exactly where it is, ahead of the loop call it feeds. Typed shows up around if branches whose two arms have to be widened to a common type (0 and 1 + deepBlockSum(prev) both get typed as Int), because it carries no structure of its own, so it's a pure pass-through.
Both examples run cleanly at a million levels deep, and the local val ends up hoisted ahead of the tailcall, not duplicated or dropped:
Step 4: More Than One Parameter
Everything so far assumes a single parameter, param, threaded through by hand. deepSumAcc needs two:
The fix is mechanical: param becomes termParams, a list read the same way, straight off the symbol, and the rename step becomes a symbol-to-symbol map instead of a single equality check:
deepSumAcc(100, 0L) sums 1 to 100 correctly, arbitrarily deep. Point the same code at a generic method:
and it breaks:
paramSymss returns every parameter clause, and a type parameter list is one of them. For deepRepeat[A], methSymbol.paramSymss is List(List(A), List(n, a)), so .flatten folds the type symbol A in right alongside the two term parameters. loop ends up with an unintended third parameter for a type, and building a Ref to it crashes outright. Filtering to term symbols fixes it:
With that, deepRepeat compiles and runs unmodified. Nothing in deepRecursiveImpl hardcodes a concrete type anywhere: param.termRef.widen and TypeRepr.of[T] read A straight off the symbols involved, and loop is created as a nested method still inside deepRepeat's scope, so a reference to A resolves exactly like it does in the original body. The decompiled bytecode confirms it isn't specialized per call site: A erases to Object, same as any other generic method would:
Step 5: using, implicit, and Context Bounds
One shape is still unhandled: a trailing parameter clause.
termParams already sees bump, because paramSymss returns every parameter clause, using included, so loop gets both parameters from the start. Compile deepWithBump and the failure is in the self-call, not the definition:
deepWithBump(n - 1) isn't a single Apply once the compiler fills in the using argument — it's a curried one, Apply(Apply(Ident(deepWithBump), List(n - 1)), List(bump)). Reading args straight off the pattern match, case (call @ Apply(_, args)), only ever sees the outermost clause List(bump) and tries to pass it as loop's first, Int parameter. Flattening the call's own argument lists fixes it:
and in buildChain, the pattern drops args entirely in favor of flattenArgs(call):
loop itself stays a single flattened parameter list (using only matters for how the caller supplies an argument, not for how loop receives it).
This one change covers more than using: an old-style implicit parameter clause desugars to the same curried shape, and so does a context bound, since def deepSumWith[A: Numeric](n: Int, a: A): A is sugar for a synthesized trailing using Numeric[A] clause:
Both compile and run against the exact same macro — no further special-casing needed. And with that, this is the complete implementation:
flattenArgs picked up the same fix as sum back at the start of this post: an accumulator parameter turns it properly tail-recursive, so @tailrec accepts it. And one more guard showed up alongside the control-flow one: deepRecursive used inside a lambda instead of a named def's body:
fails on purpose.
methSymbol.flags.is(Flags.Synthetic) catches it before any of the rest of the macro runs. Inside a lambda, Symbol.spliceOwner.owner isn't a named method with its own paramSymss. It's the compiler-generated apply method backing the closure, so f in the body refers to the val holding the lambda, never to methSymbol itself. Every self-call check downstream depends on fun.symbol == methSymbol matching; here it never would, so without this guard f(n - 1) would just fall through as an ordinary, un-trampolined call, silently as stack-unsafe as the code this macro exists to fix.
Preventing Unsafe AST Transformations
buildChain assumes every call selfCallCollector hands it runs exactly once, unconditionally, right where it was found. Two shapes break that assumption without changing what the code looks like at a glance:
The self-call sits inside a lambda passed to .map. Trampolining it the normal way means evaluating it once, up front, at the position selfCallCollector found it, but the lambda is meant to run three times, once per list element. And:
Here the self-call has to run inside the try's dynamic extent for catch to see its exceptions. The trampoline's own driver, .result, runs later and elsewhere; by the time it calls loop again, the original try has already returned.
Both would silently compile wrong under the macro from the previous section: a call count quietly changed from three to one, or a catch that stops catching. selfCallCollector closes that gap by refusing to guess:
Hitting one of these six node kinds mid-search doesn't stop the fold. It re-runs foldOverTree on just that subtree with a fresh accumulator, Nil, to check whether a self-call is hiding underneath. An empty result means the risky construct contains nothing recursive, so it's harmless and the outer acc passes through untouched. A non-empty result means a self-call sits somewhere its call count or exception handling would change if it were extracted, and compilation aborts there instead of continuing:
Both f and g above fail to compile with exactly that message, pointing straight at the offending call. So does a self-call sitting inside an if that isn't the outer branch dispatch transform already understands, like 1 + (if flag then h(n - 1, flag) else 0) — the same six-case check catches it whether the risky construct is the whole function body or three levels deep inside an arithmetic expression.
Case Closed
To be clear, deepRecursive is an experimental proof of concept. It targets direct self-recursion within a single method body. It does not support mutual recursion between separate functions, and as we saw with non-tail block statements, certain structural shapes can still bypass the macro without warning. A far more elegant long-term solution would be expanding the capabilities of @tailrec itself, either through a compiler plugin or a direct contribution to the compiler. Handling trampolining at the compiler level would eliminate the blind spots of AST macros entirely while providing a seamless, built-in experience. Even so, this experiment proves an important point: we do not need coroutines, monadic effect libraries, or Project Loom to write direct-style, stack-safe deep recursion in Scala 3. Kotlin achieved this by relying on language-level suspend functions, but Scala's metaprogramming allows us to pull off the same trick purely at compile time.
You can find the latest iteration of the macro implementation within the deepRecursiveFunction.scala source file.
