Skip to content
Kavachकवच

Recursion

Also known as: recursion recursive call itself stack overflow factorial fibonacci

● Beginner4 minBefore this: FunctionsSpec 3.8

A function may call itself, as long as each call gets closer to a case that stops.

fn factorial(n: Int) -> Int {
    if n <= 1 { 1 } else { n * factorial(n - 1) }
}

fn main() {
    print(factorial(5))
    print(factorial(20))
}

The program ran and printed:

kavach run factorial.kav

1202432902008176640000
factorial.kav: Kavach code, then what running it prints

factorial(5) is 5 * factorial(4), and so on down to factorial(1), which is just 1: the case that stops.

Too deep

Each call waits for the next, and the waiting calls take room. Far too many stop the program, cleanly:

fn depth(n: Int) -> Int {
    if n == 0 { 0 } else { 1 + depth(n - 1) }
}

fn main() {
    print(depth(1000))
    print(depth(100_000_000))
}

The program ran, then stopped with a panic:

kavach run deep.kav

1000panic: stack overflow: calls are nested too deeply (spec 3.8)
deep.kav: Kavach code, then what running it prints

How deep it can go

Each call that waits keeps its parameters and values on the stack, a block of memory that holds the calls still running. How many fit depends on where the program runs:

Where it runsStackDeepest recursion
kavach run (the interpreter)512 MB, of which it keeps 32 MB in hand to report the overflowtens of thousands of small calls, about 50,000 in a release build of kavach: measured as calls use the stack, not counted, so bigger calls go less deep
Native code: kavach build, kavach run --native512 MB for the programabout 13 million calls of a small function like depth above (measured with kavach run --native), about 36 bytes each; fewer when each call holds more values
Each task, from spawn512 MB each, of address space: memory is used only as calls need itthe same as native code
A library called from another language (kavach build --lib)256 KB below the callera few thousand small calls: the caller's own stack is unknown, often 1 MB, so a deep recursion stops well before it
A gpu fnnoneno recursion at all: it is a compile error

Past the limit, the program stops with the panic above: never a crash or corrupted memory.

For a long repetition, a for or while loop is the right tool.

ours @v0.2 · stack.rs:10 STACK_USE()ours @v0.2 · lib.rs:52 STACK_SIZE()ours @v0.2 · lib.rs:119 STACK_SIZE()ours @v0.2 · lib_calls.rs:21 LIB_STACK()

What Kavach does for you

  • Adding recursion becomes a loop

    A function that calls itself to add up a result runs as a loop, as fast as one. Nothing you can see changes: a recursion too deep for the stack still stops with the same message.

    unrecurse.rs