Tail-Call Optimization

Zym supports script-directed tail-call optimization via the @tco directive. This allows recursive functions to run in constant stack space, enabling deep recursion without stack overflow.

What is Tail-Call Optimization?

A tail call is a function call that is the last operation in a function — the return value of the called function is directly returned without further computation. When TCO is active, the runtime reuses the current stack frame instead of allocating a new one, turning recursion into an iterative loop internally.

tail call vs non-tail call

// TAIL CALL — result of factorial() is returned directly
func factorial(n, acc) {
    if (n <= 1) return acc
    return factorial(n - 1, n * acc)  // ← tail position
}

// NOT a tail call — multiplication happens AFTER the recursive call
func factorial_bad(n) {
    if (n <= 1) return 1
    return n * factorial_bad(n - 1)  // ← NOT tail position
}

The @tco Directive

TCO in Zym is opt-in via the @tco directive. Place it before a return statement or at the top of a file/function to indicate how tail calls should be optimized.

@tco directive

// Per-call annotation
func countdown(n) {
    if (n <= 0) return n
    @tco aggressive
    return countdown(n - 1)
}

countdown(1000000)  // runs in O(1) stack space

TCO Modes

Mode	Behavior	Use Case
`aggressive`	Optimizes any `return <call-expr>` in tail position, including callees the compiler cannot resolve: a function held in a variable or parameter, a dynamic callee like `arr[0]()`, or a lambda	Dynamic callees; higher-order tail calls; calls whose argument count does not match a declaration
`safe`	Optimizes only tail calls whose callee the compiler can resolve at compile-time: a call to the enclosing function’s own name, or a call to a hoisted `func` declaration (at global scope, or in any enclosing scope) whose parameter count matches the call. Any other call is left as a normal call.	Default; self-recursion and mutual recursion between declared functions
`off`	Disables TCO entirely — all calls use normal stack frames	Debugging; ensuring full stack traces are preserved

Captured locals: TCO reuses the current stack frame, which overwrites its locals. In both modes, before every tail call, the compiler closes every upvalue at or above the frame base, so a closure that captured one of those locals holds its own copy before the frame is reused. Neither mode refuses to optimize a function that creates closures.

Default mode: If no @tco directive is specified, the default mode is safe. Functions inherit the TCO mode from their enclosing scope.

mode examples

// Safe (the default) — the callee is the enclosing function itself
func sum(n, acc) {
    if (n <= 0) return acc
    return sum(n - 1, acc + n)  // optimized
}
sum(100000, 0)

// Safe (the default) — the callee is a declaration of matching arity
func helper(n, acc) {
    if (n <= 0) return acc
    return helper(n - 1, acc + n)
}

func caller(n) {
    return helper(n, 0)   // optimized — helper is hoisted, arity matches
}

// Aggressive — the callee is a value, not a name the compiler can resolve
@tco aggressive
func dispatch(table, n) {
    if (n <= 0) return n
    return table[0](table, n - 1)  // safe mode leaves this a normal call
}

Basic TCO Patterns

Accumulator pattern

The most common TCO pattern: carry a running result as an extra parameter so the recursive call is in tail position. Self-recursion resolves at compile-time, so these patterns need no @tco directive. The default safe mode optimizes them.

accumulator

func factorial(n, acc) {
    if (n <= 1) return acc
    return factorial(n - 1, n * acc)
}

factorial(5, 1)       // 120
factorial(10, 1)      // 3628800
factorial(100000, 1)  // runs without stack overflow

Deep recursion countdown

func countdown(n) {
    if (n <= 0) return n
    return countdown(n - 1)
}

countdown(1000000)   // 0 — runs in O(1) stack space

Mutual Recursion

Tail calls between different functions are optimized under the default safe mode. Every func declaration is hoisted before any body is compiled, so a call to a function declared later in the file still resolves at compile-time, and one direction of a mutually recursive pair is a forward reference by definition. Mutual recursion between declarations does not require @tco aggressive.

Even/Odd

mutual recursion — no directive needed

func isEven(n) {
    if (n == 0) return true
    return isOdd(n - 1)   // optimized — isOdd is a hoisted declaration
}

func isOdd(n) {
    if (n == 0) return false
    return isEven(n - 1)  // optimized
}

isEven(200000)   // true — no stack overflow
isOdd(200001)    // true

When aggressive is still needed: safe resolves the callee by name and arity. A cycle can also run through a value rather than a declaration: a function held in a variable, list or map, a parameter holding a callback, or a call whose argument count does not match the declaration it names. None of those resolve at compile-time, so they are optimized only under @tco aggressive.

Advanced TCO Patterns

Accordion pattern

Mutual recursion where the two functions have very different frame sizes. One function has a tiny frame (few locals); the other has a large frame (many locals). The runtime must correctly resize the frame on each tail call.

accordion pattern

func ping(n) {
    if (n == 0) return "Success"
    // Tiny frame → tail call to LARGE frame
    @tco aggressive
    return pong(n - 1)
}

func pong(n) {
    // Large frame: many local variables
    var a = 1
    var b = 2
    var c = 3
    var d = 4
    var e = 5
    var f = 6
    var g = 7
    var h = 8
    var i = 9
    var j = 10

    // Verify memory integrity
    var sum = a + b + c + d + e + f + g + h + i + j
    if (sum != 55) return "Memory corruption!"

    // Large frame → tail call to TINY frame
    @tco aggressive
    return ping(n - 1)
}

ping(1000000)   // "Success" — frames resize correctly

Shattered accordion pattern

A more extreme variant with three or more functions of different frame sizes in a mutual recursion chain. Tests that frame resizing works across multiple distinct sizes.

shattered accordion

func alpha(n, x) {
    if (n <= 0) return x
    // Tiny frame: 2 args, 0 locals
    @tco aggressive
    return beta(n - 1, x + 1, "extra")
}

func beta(n, x, junk) {
    // Medium frame: 3 args, 2 locals
    var v1 = x * 2
    var v2 = n + 1
    @tco aggressive
    return gamma(n - 1, v1, v2, "more", 42)
}

func gamma(n, a, b, c, d) {
    // Large frame: 5 args, 4 locals
    var l1 = 1
    var l2 = 2
    var l3 = 3
    var l4 = 4
    if (n <= 0) return "Success"
    @tco aggressive
    return alpha(n - 1, a / 2)
}

alpha(1000000, 1)   // "Success"

TCO with closures

TCO interacts correctly with closures. A tail-recursive function that captures variables from a closure will still be optimized, and the closure’s captured state is preserved.

TCO with closures

var history = [null, null, null, null, null]

func tortureTest(n, index, list) {
    if (n == 0) return list

    // Closure captures 'n' from the current frame
    func snap() { return n }
    list[index] = snap

    @tco aggressive
    return tortureTest(n - 1, index + 1, list)
}

tortureTest(5, 0, history)

history[0]()   // 5 — each closure captured its own 'n'
history[4]()   // 1

Interactions

TCO with continuations

TCO and delimited continuations are fully compatible. A tail-recursive function can be captured mid-recursion and resumed later — the continuation correctly restores the optimized frame state, including closures and local variables.

TCO + continuations

var TAG = Cont.newPrompt("cap-val-nested")

@tco aggressive
func test_nested(counter, stepsLeft) {
    if (stepsLeft == 0) return counter

    if (counter == 3) {
        var x = Cont.capture(TAG)
        if (x != null) counter = counter + x
    }

    counter = counter + 1
    return test_nested(counter, stepsLeft - 1)
}

Cont.pushPrompt(TAG)
var k = test_nested(0, 10)

Cont.pushPrompt(TAG)
Cont.resume(k, 5)

The function recurses with TCO (constant stack space) and pauses mid-recursion via Cont.capture. When resumed with a value, the continuation picks up exactly where it left off and TCO continues reusing frames.

Best Practices

Use accumulator parameters to ensure recursive calls are in tail position.
Choose the right mode: Stay on safe (the default) for self-recursion and for mutual recursion between declared functions. Reach for aggressive only when the callee is a value the compiler cannot resolve by name and arity.
Place @tco before the return: The directive annotates the immediately following return statement.
Verify tail position: The call must be the last operation — no arithmetic, concatenation, or other operations on the result.
Use off for debugging: TCO removes stack frames, which can make stack traces harder to read. Use @tco off during development if needed.

Common mistake: return n * f(n-1) is not a tail call because the multiplication happens after f() returns. Restructure with an accumulator: return f(n-1, acc * n).