Recursion & Tail Calls
Transcript
Made automatically from the video's sound, so it may contain mistakes. Click a line to play from there.
Welcome back to the explainer. So, after taming those runaway retry loops across networks in our last session, we're now zooming right inside a single process. Today, in the finale of our first arc on determinism, we're gonna watch self-calling functions collide head on with tiny thread call stacks.
And listen, we're skipping the basic toy factorial examples today. We are going straight to the mattle. Here's our agenda for today's explainer. Physics of the call stack, the tail call language wars, stack exhaustion and CWE674, and finally, escaping the vibecoder trap.
Let's get right into it. Right, so in pure mathematics, recursion is, well, it's elegant, isn't it? It's that pristine, overlapping subproblem logic you see in classic computer science texts.
But in the brutal physical reality of an x8664 processor, that beautiful unbounded mathematical induction translates directly into a rather violent segmentation fold. Physics of the call stack. To truly grasp why these beautiful recursive algorithms just fail in production, we absolutely have to look at the physical memory layout.
This brilliantly illustrates the sheer absurdity of our hardware limits. As mapped out by systems researcher Eli Bendersky, just look at this stark contrast. You can literally have 16 gigabytes of free heap RAM sitting there, entirely untouched, yet your entire process will violently crash because a tiny 1 to 8 megabyte thread call stack overflows.
I mean, it's wild. The anatomy of a stack frame is really the core of this problem. Every single time a function calls itself, it pushes an 8 byte return address, spilled registers, and local variables onto this tiny fixed size stack.
And this is all tracked by the stack pointer and base pointer. Now, there is a 128-byte red zone optimization at the bottom for leaf functions to use, without adjusting the pointer, but ultimately, every single call eats into that unforgiving physical space.
To put that into perspective, in C Python, you only get about a thousand frames before a hard-coded guard throws a recursion error. And that's specifically just to prevent a raw C-level segmentation fault. Meanwhile, the V8 JavaScript engine, it gives you roughly 10,000 frames before dying with a maximum call stack size exceeded error.
The physical space is just incredibly unforgiving. The tail call language wars. Because this strict physical limit didn't just cause crashes, it sparked one of the greatest philosophical conflicts in the history of programming language design.
On one side of the battlefield, we have Guy Steele and the scheme standard. They argue that proper tail calls, or PTC, are a fundamental feature. Their contract guarantees that if a function returns the result of calling itself, the compiler executes it in constant O1 stack space.
Languages like Lua and Elixir's Beam embrace this implicitly, and Kotlin actually verifies it at compile time. You also have opportunistic compiler optimization, like using GCC with the O2 flag, which might pass fine in a release build by optimizing sibling calls, but then it'll immediately crash your unoptimized debug builds.
I'll talk about a headache. But on the exact opposite side, we have Guido Van Rossum, who deliberately rejected implicit tail call optimization for Python. His argument, and this is a view widely shared by the V8 JavaScript team, by the way, is that secretly eliminating stack frames completely ruins tracebacks.
If those frames are gone, developers lose their debugging context when an error is thrown in production. And honestly, who wants to debug production without a stack trace? The crucial takeaway here is that even with tail calls, it is incredibly easy to accidentally break the optimization.
A proper tail position simply returns the recursive call. But the very second you add a mathematical operation, like returning one plus the recursive call, or using an await, or wrapping the whole shebang in a try-finally block, you've created a non-tail trap.
And a quick warning: even if you use top-down memoization, like Python's Funk Tools cache, a cold call to a deep tree will still blow the call stack instantly. The frames aren't dropped, so that memory's quickly exhausted. This debate literally split the web browser engines in two.
Safari's WebKit actually went ahead and implemented the ECMAScript 6 tail call spec, but they had to invent a side stack, brilliantly named Shadow Chicken of all things, just to keep up to 128 deleted frames for debugging. Meanwhile, Chrome's V8 and Firefox's SpiderMonkey explicitly rejected the spec, citing cross-realm security issues, and the fact that it just made standard debugging an absolute nightmare.
Stack exhaustion and CWE674. Let's see how all this theory builds into real-world security vulnerabilities, because when developers ignore the physics we just talked about, bad things happen. CWE674, uncontrolled recursion.
Basically, when an application doesn't strictly control recursion depth, attackers can feed it deeply nested payloads to maliciously exhaust the thread stack. This causes an immediate full-scale denial of service. Game over.
And these aren't just theoretical bugs. Real-world passers in Go were blown up by deeply nested arrays, triggering panics even on Go's famously growable stacks. Rust's heavily used SER JSON library had to implement strict 128-level nesting guards to stop attackers in their tracks.
Over in the web ecosystem, GraphQL query bombs exploit A to B to A parent cycles to crash servers. Bottom line, if you pass data recursively, you are vulnerable. Escaping the Vibecoder trap.
This is a massive pitfall waiting for software engineers who rely heavily on AI code generation. We call this the Vibecoder trap. You see, large language models naturally write mathematically elegant, unbounded recursive traversals.
Whether it's mapping an org chart, walking an abstract syntax tree, or writing N plus one recursive ORM queries. The code looks absolutely beautiful in your pull request. But the AI is completely oblivious to the fact that your production engines will crash the moment real user-driven data actually scales up.
So, how do we fix it? Well, to fix this manually, you have to shift the burden from that tiny call stack to that massive 16GB heap RAM. You can build a continuation passing style trampoline.
Essentially, instead of calling the function, you wrap your tail calls in anonymous lambdas, often called thunks, and return them up to a while loop. The trampoline loop then executes the thunks safely on the heap, keeping your call stack perfectly flat.
But let's be honest, manually writing trampolines in standard business logic creates incredibly unreadable code. The real solution is what we call the judicious AI prompting playbook. Whenever depth is data-driven, you absolutely must mandate that your AI uses explicit heap work lists, like DEX or arrays.
You must enforce visited cycle sets. You have to implement strict max depth caps, say 32 levels. And for databases, push the work to PostgreSQL using its recursive cycle safety. Forbid those unreadable manual trampolines on shallow, schema-bounded trees.
You have to explicitly stop the AI from writing infinite recursion. Oh, and just as a fascinating side note, for those of you in systems programming, you can actually bridge this gap using segmented stacks. Tools like Rust's stacker crate check if you're within a 32 kilobyte red zone of your stack limit.
If you are getting too close, it dynamically allocates a fresh one-megabyte stack segment right on the heap, letting the closure run safely. It's just a brilliant blend of performance and safety. So that wraps up our deep dive into the physics of recursion and the single process limit.
But I'll leave you with this final provocative thought. If computer scientists and language designers can't even agree on the physical shape of a single process call stack, how on earth do we agree on what time it is across a massively distributed system?
Next time on the Explainer, we open arc 2, time, clocks, and time zones. Because if single process memory is this messy, just wait until we look at distributed time. See you then.