The Recursion That Was a Loop

Here is a small Koru program — a register machine, decoding one instruction per step until the program counter runs off the end:

run = if(pc >= n or pc < 0)
| then => done { a, b }
| else |> capture { ... }
    ! as s |> captured { ... }              // decode the instruction (pure arithmetic)
    | captured r |> run(pc: r.np, a: r.na, b: r.nb, ops, regs, offs, n)
        | done res => done res

The run flow re-enters run. It computes the next state, hands control back to itself, and returns whatever that produces. At the implementation level, this is a function calling itself — recursion.

And we were compiling it like recursion. That turned out to be the bug. Not a correctness bug — a the-compiler-doesn’t-understand-what-this-is bug.

What it cost

Koru events carry their inputs in a struct. The run event’s input includes the program — three [8]i64 arrays for opcodes, registers, and offsets. So every recursive step reconstructed that input by value:

const result = run_event.handler(.{ .pc = r.np, .a = r.na, .b = r.nb,
                                     .ops = ops, .regs = regs, .offs = offs, .n = n });
return .{ .done = result.done };

At ReleaseFast on ARM64, that lowers to a real recursive call with a ~1.4 KB stack frame and a fistful of memcpys per step — a 224-byte copy of the whole input, plus the arrays. The copy is real; LLVM does not elide it. Two things follow:

1. The stack grows linearly with the number of steps. A small input is fine. A large one is a stack overflow waiting to happen.
2. Every step copies the payload, even though the program never changes.

On a register-machine benchmark, this idiom ran about 2.6× slower than the same machine written naively in Rust — a while loop with the arrays borrowed by reference.

What it actually is

Look again at the shape:

run = if(pc >= n or pc < 0)
| then => done { a, b }     // exit
| else |> ... |> run(...)   // re-enter with new state
    | done res => done res  // forward the result, unchanged

The self-call sits in tail position. After it returns, the only work left is to hand its result straight back up. Nothing is held on the stack across the call; no results are combined; the call depth is pure overhead. The frames exist only to wait for the next frame to finish and forward its answer.

That is a loop. Spelled as recursion, but a loop:

while not base:
    state = step(state)
return state

So the fix isn’t to make recursion faster. It’s to recognize a flow that re-enters its own event in tail position — with the result forwarded unchanged — and lower it to an actual loop:

pub fn handler(__koru_event_input: Input) Output {
    var pc = __koru_event_input.pc;
    var a = __koru_event_input.a;
    // ... ops, regs, offs, n bound as `var` too
    __koru_self_loop: while (true) {
        if (pc >= n or pc < 0) return .{ .done = .{ .a = a, .b = b } };
        // decode ...
        pc = r.np; a = r.na; b = r.nb;   // reassign only what changed
        continue :__koru_self_loop;       // ops/regs/offs/n stay put — never copied
    }
    unreachable;
}

The state lives in mutable locals. Each iteration reassigns only the values that change; the invariant arrays sit in their slots, untouched, never copied. The base case returns straight out of the loop. No stack growth, no per-step copy. Detection is conservative — if the shape doesn’t provably match, the compiler falls back to the ordinary call. A miss is slow, never wrong.

The number that was too good

Then we benchmarked it, and the register machine went from ~1500 ms to ~40 ms. A 38× win. It even came out faster than the naive Rust.

That is exactly the moment to stop trusting your benchmark.

You do not beat naive, hand-written Rust by an order of magnitude on identical work. So we pulled the binary apart — and the register machine’s arithmetic wasn’t in it. The decode loop was gone. What happened is that once the idiom became a real loop over a compile-time-known program, LLVM did the obvious thing: it evaluated the entire machine at compile time and emitted the answer as a constant. The “38×” wasn’t the loop running faster. It was the optimizer deleting the loop.

Write the equivalent Rust so it can fold too — program as a const, read directly instead of through a borrow — and it collapses to the same ~0.01s. It was never “Koru beats Rust.” It was “foldable code folds, in both languages, and our benchmark was foldable.”

The actual win

Here’s the part worth keeping. The recursive version could never have folded. LLVM cannot see through a self-call carrying a by-value payload — the computation is opaque to it. The loop version is transparent. So the lowering didn’t just remove a copy and a stack frame; it moved the whole idiom from “the optimizer can’t touch this” to “the optimizer can constant-fold it.”

That’s the real result, and it’s not a headline multiplier:

• When the program is known at compile time, the machine folds to a constant — parity with the equivalent Rust loop, which is to say, the runtime work disappears.
• When the program is genuinely runtime data (folding impossible), the loop is roughly 3× faster than the old recursive form — the cost we removed was the per-step copy and the stack churn.

The natural way to write this in Koru — a flow that continues into itself — now optimizes like the natural way to write it in Rust. The programmer didn’t have to reach for a special loop construct, or hand-thread the arrays by pointer to dodge a copy. They wrote the obvious recursive-looking flow, and the compiler recognized the loop hiding inside it.

A loop on any target

Here is the part that makes this more than a native-backend trick. The recognition happens at the Koru level — the compiler decides “this is a loop” — not down in some backend’s optimizer where we cross our fingers and hope it notices. And a tail self-continuation is a loop no matter what it eventually compiles to.

That distinction matters most on a target that can’t save itself. Koru’s JavaScript backend is the most experimental corner of all this — but JavaScript has no tail-call optimization, full stop. On the native side, LLVM can sometimes rescue a tail call; on JavaScript there is no rescue. Written as recursion, a deep self-continuation simply grows the call stack until it overflows, and no runtime will catch it.

But if the compiler has already identified the loop, none of that is the host’s problem anymore. There is nothing stopping these recursive-looking Koru patterns from running as flat, stack-safe loops in JavaScript — not because V8 got cleverer, but because the recursion was never the essential thing. It was a spelling. The loop underneath it is portable in a way the stack frames never were.

Why this keeps happening to us

We’ve written before that Koru is hard to benchmark, because it tends to delete categories of runtime work rather than do them faster — and that head-to-head numbers miss the point when the work isn’t there anymore. This is that thesis in miniature, found by accident. The most honest benchmark of this change is not “2.6× slower became Rust-parity.” It’s “the work folded away.”

The lesson we keep relearning: a suspiciously good number is a clue, not a victory. Chase it down. Half the time it’s a measurement artifact, and the other half — like here — the artifact is pointing at something truer than the number you were trying to measure.