Each call pushes a frame. The base case stops the growth. Returns unwind the stack back up.
Recursion is where a lot of engineers first feel the click of computer science being beautiful — a function that solves a problem by calling itself, and somehow it works. It’s also where a lot of engineers first meet a RecursionError or a segfault at 3am. Both experiences come from the same mechanism: the call stack. Understanding it turns recursion from a party trick into a tool you can reach for deliberately, and turns “stack overflow” from a scary crash into an obvious, predictable consequence.
What actually happens: the call stack
Every time a function is called — recursive or not — the runtime pushes a stack frame onto the call stack. That frame holds the function’s local variables, its arguments, and the return address (where to resume when it finishes). When the function returns, its frame is popped and control goes back to the caller.
Recursion just means a function’s frames stack up on itself. Follow the diagram with fact(4) (factorial). fact(4) needs fact(3) before it can multiply, so it pushes a frame and calls it. fact(3) needs fact(2), and so on down. The frames pile up, each one paused mid-computation, waiting on the one below it. Then fact(0) hits the base case — the condition that returns without recursing further — and the whole thing unwinds: 1, then 2, then 6, then 24, each frame completing its multiplication and popping off.
Two parts are non-negotiable for a correct recursion:
- A base case — the stopping condition. Without it, the function calls itself forever.
- Progress toward the base case — each call must move closer to it (here, the argument shrinks by one).
Get either wrong and you get infinite recursion.
Why it overflows
The call stack is a finite region of memory. Every pending recursive frame consumes some of it, and when the frames pile up past the limit, you get a stack overflow — the runtime runs out of stack space and the program dies (a RecursionError in Python, which caps recursion around 1000 by default; a crash in C). The right side of the diagram is the whole failure mode: no base case, or a base case too deep to reach, and the stack grows until it hits the wall.
This is why deep recursion is dangerous in production. A tree that’s usually shallow but occasionally 50,000 nodes deep, a recursive parser fed a pathological input, a graph walk on an unexpectedly large structure — these blow the stack in production on inputs you never saw in testing. The fix is almost always one of two things:
- Convert to iteration with an explicit stack. Any recursion can be rewritten as a loop that manages its own stack data structure on the heap (which is large) instead of the call stack (which is small). Uglier, but bounded by available memory, not by stack depth.
- Tail-call form, where the language supports it. If the recursive call is the last thing the function does, some languages (Scheme, and with optimizations others) reuse the current frame instead of pushing a new one, turning the recursion into a loop under the hood. Notably, Python and Java do not do this — so in those languages, deep recursion is a real hazard and iteration is the safe answer.
Where recursion is the right tool
Recursion isn’t just risky elegance — for some problems it’s the natural fit, because the problem itself is recursive:
- Trees and graphs. Traversing a file system, a DOM, a syntax tree, or any hierarchy is naturally recursive: “process this node, then recurse into its children.” We’ll see this again in graph traversal.
- Divide and conquer. Merge sort, quicksort, binary search — split the problem in half, solve each half recursively, combine. The recursion depth here is O(log n), which is shallow and safe.
- Parsers and interpreters. Recursive-descent parsing mirrors the recursive structure of a grammar almost line for line.
The rule of thumb: recursion shines when the recursion depth is bounded and shallow (like O(log n) divide-and-conquer) and becomes a liability when depth can grow linearly with input size (like walking a possibly-deep linked structure).
The AI-era relevance
Agent loops are recursion with a fuzzier base case. An agent that plans, acts, observes, and then plans again based on the result is running a recursive-ish loop, and it has the exact same critical requirement: a base case and guaranteed progress. An agent with no solid stopping condition is the runaway-recursion bug wearing a language model — it loops indefinitely, burning tokens and money, never converging. This is why production agent frameworks enforce hard limits on iteration depth and cost: they’re the sys.setrecursionlimit of the agentic world, a guard against a missing base case. The production failures of agentic systems are full of this pattern.
Recursive data structures are everywhere in AI plumbing. Nested JSON from tool calls, tree-structured plans, hierarchical document chunking for RAG, dependency graphs — all naturally processed recursively, and all capable of surprising you with unexpected depth on real-world inputs. A recursive JSON walker that’s fine on your test payloads can overflow on a deeply nested response from some API you don’t control.
The takeaway
Recursion is a function expressed in terms of itself, and the call stack is the machinery that makes it work — each call a frame, the base case the floor, the return path the unwind. Its elegance and its danger are the same fact: frames accumulate, and the stack is finite. Reach for it when the problem is genuinely recursive and the depth stays shallow; convert to iteration when depth can grow with your input; and in the agentic world, remember that “guarantee a base case and forward progress” isn’t just advice for factorial — it’s what keeps an autonomous loop from running forever.