RECURSION A MILLION DEEP

A capsule may call itself. Satellite runs that call in one of two ways, depending on where it stands, and knowing which is which tells you what a deep recursion costs.

The last line: a loop

When a capsule’s call to itself is the very last thing it does, there is nothing left for that level to do once the call returns — so satl does not keep the level at all. It lets the capsule’s frame go and runs the body again with the new arguments. That is a tail call, and it runs in constant memory, however many times it goes round:

satellite.include(satellite)

satellite.capsule count_down(satellite.variable.number n)
{
    satellite.statement.if(n == 0)
    {
        satellite.console.display("lift off")
    }
    satellite.statement.else
    {
        count_down(n - 1)
    }
}

satellite.capsule satellite.main()
{
    count_down(1000000)
    satellite.return(satellite)
}

lift off

A million turns, and the program uses no more memory at the end than it did at the start. The call is last in the else, and the else is last in the capsule, so it is still the last thing the capsule does.

Work after the call: a stack of waiting levels

When a capsule still has work to do after its call to itself returns, each level has to wait for the one below it. That is ordinary recursion, and each waiting level takes a few kilobytes of memory:

satellite.include(satellite)

satellite.capsule sum_to(satellite.variable.number n)
{
    satellite.statement.if(n == 0)
    {
        satellite.return(0)
    }
    satellite.variable.number below = sum_to(n - 1)
    satellite.return(below + n)
}

satellite.capsule satellite.main()
{
    satellite.console.display(sum_to(100))
    satellite.console.display(sum_to(100000))
    satellite.return(satellite)
}

5050
5000050000

sum_to(100000) keeps a hundred thousand levels waiting at its deepest, and hands every one of them back on the way up.

How deep can it go?

As deep as memory allows. Every capsule call checks how much of its stack is left, and when less than a megabyte remains, satl carries on in a fresh piece of memory and comes back to the old one when the call returns. A million levels of ordinary recursion takes about five gigabytes while it is that deep, and gives all of it back on the way up. Before 2026-09-25 it crashed at around six hundred thousand.

So both shapes work, and the difference is cost:

• A call as the last line is a loop: no extra memory, however deep.
• A call with work after it takes a few kilobytes a level while it waits.

When a recursion might go very deep — walking a long list, counting down from a big number — put the call last. When it has to combine the answers on the way back up, as sum_to does, write it the natural way and let satl find the room.

A call inside satellite.return(...), such as satellite.return(sum_to(n - 1) + n), is ordinary recursion too: the addition is work left after the call.

Where next

CAPSULES covers capsules from the start, and A SYNTAX TREE OF OBJECTS uses recursion to walk a tree.