You trampoline a recursion whose work happens after the recursive call returns; why does it still need memory proportional to depth?

## The shape a trampoline alone cannot flatten A trampoline works by letting a step **finish** and hand back a description of the next call. That is only possible when the next call is the last thing the step does. Now take the other shape: a step in an approval chain that must add its own amount to the total of everything after it. It calls the rest of the chain, waits, and then adds. The addition is unfinished work, and unfinished work means the step cannot return — so there is nothing to hand a loop. Wrapping the inner call in a description changes nothing here, because the step would have to invoke that description itself in order to get a number to add to. So the first move is not the trampoline at all. It is making the pending work **explicit**. ## Turning the leftover into a value The leftover — *whatever comes back, add my amount to it, then do whatever my own caller was going to do* — is a function of one argument. Name it, pass it along as an extra parameter, and you have **continuation-passing style**: every step receives the rest of the computation as a value and hands its result to that value instead of returning it. 1. **Name the leftover.** Turn `my amount + result of the rest` into a one-argument function: given the result of the rest, produce the final answer. 2. **Pass it down.** The step stops waiting for a result. It invokes the next step with a *larger* continuation — the one it was given, wrapped in its own addition. 3. **Bounce it.** Every call is now a step's last act, so each one can be returned to a driver loop as a description rather than performed. The base case no longer returns a number to a caller. It hands its number to the continuation it was given, which is the only thing that knows what to do with it. ## Where the depth actually went Let n be the number of steps in the chain. The pending additions did not evaporate; they were relocated. Before, n pieces of unfinished work sat inside n unfinished invocations. After, they sit in a chain of n continuation values, each holding the amount captured from its own step and a reference to the continuation it wraps. | | direct recursion | after the transform | |---|---|---| | where pending work lives | inside unfinished invocations | inside continuation values | | how much, for n steps | n pieces | n pieces | | how it is reached | returning through every caller | applying the outermost continuation | | what a too-long chain does | exhausts a small fixed region abruptly | exhausts a large growable one, or survives | | how to make it smaller | restructure so nothing is pending | restructure so nothing is pending | The last row is the honest one: the transform changes *where* depth is paid, not *whether*. The gain is real all the same — the region it moves into is typically far larger, it grows on demand, its use can be measured while the job runs, and exhausting it is an allocation failure you can see approaching rather than a collapse at a depth nobody chose. - If nothing is pending after the recursive call, no continuations are built and only the latest description is live. That is the genuinely constant-space case, and it is the one to aim for first. - If something is pending, expect memory proportional to depth, whatever shape the rewrite takes. - A step that captures a large value into its continuation keeps that value alive for the whole run, so a cheap-looking step can be an expensive link in the chain. ## The trap at the end of the chain Once the base case hands its result to the continuation, the whole chain has to be applied: the innermost continuation calls the one it wraps, which calls the one *it* wraps. If those applications are ordinary calls, the unwind is a recursion n deep — the same collapse, relocated to the end of the run, where a short test chain will never expose it. A trampolined design has to bounce here too: applying a continuation must **return** a description to the driver loop rather than call the next continuation directly. Then the unwind is n further turns of the same loop. This single detail is what separates a design that survives the longest chain anyone can construct from one that survives the demo. ## What to check before trusting it - Is anything actually pending after the recursive call? If not, do the simpler rewrite; continuations are not needed and cost more. - Does every continuation application go back through the loop, including the final unwind? - Does memory grow with input, and is the largest realistic input inside that budget? - Is the chain length genuinely unbounded, or bounded by something you control? - Has it been run against a chain longer than any depth the fixed region could ever have held?