Thinking Recursively: The Call Stack Made Concrete

Every textbook introduces recursion with the same sentence: a function that calls itself. And every junior engineer quietly trips on it, because the sentence sounds like a paradox. If the function hasn't finished running, how can it start again? Won't its variables collide with its own variables? Won't it just loop forever?

Here is the reframe this whole lesson hangs on: a recursive function never calls itself. It calls a fresh copy of itself, with its own parameters, its own local variables, its own place to stand. The original doesn't restart. It pauses, mid-flight, at the exact line of the call, and waits for the copy to come back with an answer.

The machinery that holds a paused function's entire world while any number of copies run is something this course has already named. Lesson 6 built stacks, and gave one beat to "the most famous stack": the one running your programs right now. This lesson opens that machine up. And lesson 1 left a promissory note we can finally cash: a function that recurses n levels deep is using O(n) memory even though no line of it ever allocates anything. By the end of this page, both promises are paid and recursion is what the module's title says it is: bookkeeping you can see.

Every call pushes a frame

Start with no recursion at all, because the machinery isn't special to recursion. Every function call, every single one, pushes a stack frame onto the call stack. A frame holds three things:

• the parameters the function was given,
• the local variables it creates,
• the return address: the exact spot in the caller to resume from.

Three plain functions, no recursion anywhere:

function main():               function ship(order):            function charge(amount):
    ship(order_42)                 total = price(order)             # ...talk to Stripe...
                                   charge(total)

While charge is running, the stack holds three frames. At the bottom, main's frame, paused at its call to ship. Above it, ship's frame, holding the local total, paused at its call to charge. On top, charge's frame, the one actually executing. When charge returns, its frame pops, and execution lands precisely at ship's saved return address, with total still sitting there untouched.

That's the whole trick. A frame is a paused function's entire world: where it was, and what it knew. Push on call, pop on return, and the function that must finish next is always the one that was called most recently. That is not a new discipline; that is lesson 6's stack contract, run by the runtime, millions of times per second. Recursion adds exactly one twist: several frames on the stack happen to belong to the same function. The "copies" from the opening paragraph are frames.

factorial(4), frame by frame

The marquee demo. Factorial of n is n times factorial of n minus one, and factorial of 1 is 1:

function factorial(n):
    if n == 1: return 1              # base case: small enough to answer directly
    return n * factorial(n - 1)      # one step, plus a smaller copy of the problem

Call factorial(4) and watch the stack, one motion at a time:

Three things worth staring at. First, the trip down does no arithmetic at all; it just stacks up paused frames, each holding its own n and its own position. All the multiplication happens on the unwind. Second, every partial result lives in a frame: the "memory" of being halfway through 4 * ... is not stored anywhere you wrote; it's stored in the frame the runtime pushed for you. Third, the peak is four frames deep. Depth n input, depth n stack. Hold that; it becomes the space bill below.

There is no magic left to explain. That table is recursion, all of it.

The two rules

Every recursion that works has exactly two ingredients, and the factorial walkthrough used both:

1. A base case. An input small enough to answer directly, with no recursive call. n == 1: return 1.
2. Progress. Every recursive call must move its input strictly closer to the base case. n - 1 walks toward 1.

Delete rule one and run it. factorial(1) calls factorial(0), which calls factorial(-1), then -2, forever. Each call pushes a frame, no call ever returns, and the memory reserved for the stack is finite. The push that doesn't fit kills the program: stack overflow, the most famous error in programming, famous enough that the largest Q&A site for programmers named itself after it.

How much room do you get before the crash? It's platform-dependent, but the usual numbers:

Two rows deserve commentary. Python doesn't wait for the real overflow: CPython frames ride on the C stack, and the interpreter would rather throw a clean exception at a thousand frames than let the C stack blow through its region and segfault. The limit is adjustable with sys.setrecursionlimit, but the message it encodes is honest: deep recursion is not idiomatic Python. Go is the interesting exception in the other direction: goroutine stacks start tiny, a few kilobytes, and the runtime grows them on demand by allocating a bigger block and copying, the same grow-and-copy move you built into the dynamic array in lesson 3, applied to stacks. That's a big part of why a million goroutines are affordable, and why runaway recursion in Go dies with a useful panic instead of eating the machine.

Miss rule two and you get the same crash with a subtler face: a base case that exists but that the calls never approach. factorial(n) calling factorial(n), an off-by-one that skips over the base case, or, as we'll see in the code section, a filesystem walk that follows a symlink loop.

The recursive leap of faith

Now the part that changes how you write code, because experienced engineers do not write recursion by tracing frames. We traced factorial once to prove the machinery is trustworthy. From here on, trust it.

To write a recursive function you design exactly two things: the base case, and one step, written as if the recursive call already returns the right answer. That move is called the recursive leap of faith, and it isn't faith at all; it's induction wearing work clothes. If the smallest input is handled correctly, and every input is handled correctly whenever the slightly-smaller one is, then all of them are correct. You never need to picture seventeen frames. You need to verify two short statements.

Apply it to a problem with real structure: the total size of a directory, the thing du computes when you're hunting whatever ate your disk. What is the size of a directory? The sizes of the files directly inside it, plus the sizes of its subdirectories. And the size of a subdirectory is the same question, one level smaller. The definition refers to itself, so the function gets to as well:

function dir_size(path):
    total = 0
    for entry in list_dir(path):
        if entry is a file:       total += file_size(entry)
        if entry is a directory:  total += dir_size(entry)     # the leap
    return total

Check the two rules. Base case: it's implicit here, and that's common with structural recursion; a directory containing no subdirectories runs the loop without ever recursing. Progress: every call descends one level, and a directory tree (absent cycles) has a bottom. Both statements hold, so the function is correct, and at no point did we simulate the stack.

Nested data is recursion's home

Factorial is a teaching toy; a loop computes it better (next section makes that precise). Where recursion earns its keep is data whose definition refers to itself:

• A comment thread: a comment is text plus a list of replies, and each reply is a comment. Reddit's entire UI is this definition, rendered.
• A JSON value: possibly an array of values, possibly an object whose fields hold values.
• A filesystem: directories containing directories.
• An expression in a compiler: (a + b) * c is an expression containing expressions. Every compiler you have ever used spends its life recursing over shapes like this.
• A component tree: React components rendering components rendering components.

For self-similar data, the recursive function is barely even code; it's a transcription of the data's own definition. Render a comment, then render each of its replies, and the nesting handles itself to any depth.

There's a production edge to this. If your parser recurses over attacker-supplied input, then their nesting depth becomes your stack depth, which makes "deeply nested JSON" a denial-of-service vector. This is why serious parsers cap depth: serde_json, Rust's standard JSON library, refuses input nested beyond 128 levels by default, and most hardened parsers ship a similar limit. That configuration value is this lesson's crash, priced in ahead of time by a library author who has met it. (V8's JSON.stringify on a deeply nested object throws the same RangeError as runaway recursion, for the same reason.)

One pointer forward: lessons 13 and 14 introduce trees, the data structure that is nesting, and recursion will be the native language there. This lesson runs first because of that.

Any recursion can become a loop

Time for the honest comparison, because mechanically, any recursion can be rewritten as iteration. The call stack is just a stack, and lesson 6 taught you to build one. So manage it yourself: a loop plus an explicit stack of pending work.

function dir_size_iterative(root):
    total = 0
    pending = stack containing [root]
    while pending is not empty:
        path = pending.pop()
        for entry in list_dir(path):
            if entry is a file:       total += file_size(entry)
            if entry is a directory:  pending.push(entry)
    return total

Same algorithm, same answer (the directories get visited in a different order, which a sum doesn't care about). The frames became strings you push by hand.

So which do you write? The honest scorecard:

• Linear processes: the loop wins outright. Factorial, summing a list, find-in-array. The iterative factorial is two lines, no frames, no depth limit, no call overhead. Recursion buys nothing when nothing branches; it just rents stack space to do what a for loop does for free.
• Branching and nested structure: recursion wins on clarity. Look at what the iterative walk really is: the same recursion with the bookkeeping done by hand. The runtime was already doing that bookkeeping, faster than your hand-rolled version and with less code.
• Switch to the explicit stack when depth is dangerous. Attacker-controlled nesting. Structures thousands of levels deep in a language with a 1000-frame budget. That's not a style preference; that's the platform table from the two-rules section telling you the recursion will die in production.

Tail calls, honestly

One beat on a term you will hear, so you can price it correctly. Look at factorial's recursive line: n * factorial(n - 1). After the inner call returns, there is still work pending (the multiply), so the caller's frame must survive. But suppose the recursive call were the function's very last act, with nothing pending after it. Then the frame holds nothing worth keeping, and a smart compiler can reuse the current frame instead of pushing a new one. That's a tail call, and eliminating the frame is tail call optimization (TCO): recursion in O(1) stack.

The status report, language by language, because this is where people get burned. Scheme guarantees TCO in its spec; looping in Scheme literally is recursion. JavaScript wrote proper tail calls into the ES2015 spec, and the engines mostly never shipped it: JavaScriptCore (Safari) did, V8 implemented it behind a flag and then removed it. Python rejects it on principle; Guido van Rossum has written that he wants stack traces to show the real call history. Go makes no promise either. So the working rule for a backend engineer is blunt: in Python, JavaScript-in-practice, Go, and Java, assume every call costs a frame, and when the depth is linear, write the loop.

The space bill

Lesson 1's promissory note, now due: a function that recurses n levels deep is using O(n) memory even though no line of it ever allocates anything. You've now seen exactly why. At the peak of factorial(n), n frames are alive simultaneously, each some tens to hundreds of bytes of parameters, locals, and return address. Recursion depth is an allocation. From today, price it like one, next to every other space cost in your analysis.

The flip side sets up the next two lessons. Depth depends on how fast the problem shrinks. Shrink by one per call (factorial, walking a linked list recursively) and depth is n: the dangerous kind. Shrink by half and depth is log n: binary search written recursively costs thirty frames against a billion elements, harmless, which is why last lesson could shrug and say "nobody writes it recursively, but you could". And merge sort, next lesson's star, also recurses by halving: about twenty levels of frames for a million elements. Halving recursion barely touches the stack. Minus-one recursion is the kind that meets the platform table.

The duplicated-work trap

One trap left, and it isn't about the stack. Here's Fibonacci, written straight from its definition:

function fib(n):
    if n <= 1: return n
    return fib(n - 1) + fib(n - 2)

Two recursive calls per invocation, which means the calls no longer form a chain. They form a tree. Trace fib(5): it calls fib(4) and fib(3). But fib(4) also calls fib(3). So fib(3) is computed twice, from scratch, identical work. fib(2) runs three times, fib(1) five times, and the duplication compounds at every level: the tree roughly doubles per level of n. That is lesson 1's exponential rung, the O(2ⁿ) row of the ladder labeled "the universe ends first", reached by accident in four lines. fib(50) written this way makes on the order of tens of billions of calls: minutes of CPU for a number that fits in eight bytes.

The subtle part: the stack is fine. The tree is explored one branch at a time, so the depth never exceeds n. Exponential time, linear space; the two bills are separate, and this function runs up only one of them.

The lesson is sharp and worth memorizing: recursion describes a problem; it does not promise an efficient solution. The fix, remembering answers instead of recomputing them, is called memoization, and it opens a door (dynamic programming) big enough that dsa-patterns gives it its own treatment. For now, learn the smell: two or more recursive calls over overlapping inputs means audit before you ship.

The walk, in real code

The videos stay in pseudocode; here is dir_size, the lesson's working example, in the three languages this course carries. The TypeScript version uses Node's synchronous APIs to keep the shape visible.

import { readdirSync, statSync } from "node:fs"
import { join } from "node:path"
 
function dirSize(path: string): number {
  let total = 0
  for (const entry of readdirSync(path, { withFileTypes: true })) {
    const full = join(path, entry.name)
    if (entry.isDirectory()) total += dirSize(full) // the leap of faith
    else if (entry.isFile()) total += statSync(full).size
  }
  return total
}

func dirSize(path string) (int64, error) {
	entries, err := os.ReadDir(path)
	if err != nil {
		return 0, err
	}
	var total int64
	for _, e := range entries {
		full := filepath.Join(path, e.Name())
		if e.IsDir() {
			sub, err := dirSize(full) // the leap, with errors carried up
			if err != nil {
				return 0, err
			}
			total += sub
		} else {
			info, err := e.Info()
			if err != nil {
				return 0, err
			}
			total += info.Size()
		}
	}
	return total, nil
}

#include <filesystem>
namespace fs = std::filesystem;
 
std::uintmax_t dir_size(const fs::path& dir) {
    std::uintmax_t total = 0;
    for (const auto& entry : fs::directory_iterator(dir)) {
        if (entry.is_directory()) total += dir_size(entry.path());
        else if (entry.is_regular_file()) total += entry.file_size();
    }
    return total;
}

Read the TypeScript version against the two rules. readdirSync lists one directory. Files add their size. A subdirectory triggers the recursive call, and we trust it to return that subtree's total, because base case plus progress hold: a directory with no subdirectories never recurses, and every call moves one level down a finite tree.

The Go version is the same skeleton, plus Go's signature move: errors propagate up the same path the partial sums come down. A permission failure five levels deep pops frame by frame to the caller, riding the exact unwind mechanism the factorial table showed.

And the explicit-stack iterative equivalent, in TypeScript, so you can see the correspondence in real code once:

function dirSizeIterative(root: string): number {
  let total = 0
  const stack: string[] = [root] // lesson 6's structure, in user space
  while (stack.length > 0) {
    const path = stack.pop()!
    for (const entry of readdirSync(path, { withFileTypes: true })) {
      const full = join(path, entry.name)
      if (entry.isDirectory()) stack.push(full)
      else if (entry.isFile()) total += statSync(full).size
    }
  }
  return total
}

Line for line it's the recursive version with the runtime's job done by hand: the call became a push, the frame became a string, the return became the next iteration of the loop. The standard libraries know this correspondence too: C++ ships the iterative walk under the name std::filesystem::recursive_directory_iterator, and Node's readdirSync(path, { recursive: true }) does the same job without growing the call stack.

Two honest footnotes on all four versions. First, none of them follow symlinks into directories (the APIs above report a symlink as a symlink, not a directory), and that's not an accident: a symlink cycle would break rule two, progress, and recurse forever; real du tracks visited inodes for exactly this reason. Second, recursion depth here equals the deepest directory nesting, which on a real filesystem is dozens of levels at most. Comfortably inside every budget in the platform table, which is why the recursive version is the one people actually write.

Where this shows up in production

Beyond du and the parser depth caps already covered: every compiler and linter you run is recursion over expression trees (an expression contains expressions, so the type checker that handles (a + b) * c is the leap of faith applied to syntax). React's render is conceptually a recursive walk of the component tree. JSON.stringify and every serializer like it recurse over nested values, which is why they throw on cycles and on pathological depth. And Go's tiny-but-growable goroutine stacks are a runtime team explicitly engineering around this lesson's space bill. The pattern to internalize: wherever data nests, the code that processes it either recurses or carries an explicit stack; there is no third option.

What's next

The machinery is open: a call pushes a frame holding parameters, locals, and a return address; a return pops it; recursion is just frames of the same function; writing one is two design decisions, a base case and one trusted step; depth is memory; halving makes depth cheap; and two innocent calls can hide an exponential bill. Next lesson, this machinery meets the most studied problem in computer science: sorting. The fastest general-purpose sorts are recursive at heart. Merge sort splits the array in half, trusts each half to come back sorted, and earns everything in how it puts them back together, twenty frames deep at a million elements. Quicksort makes a braver bet. And the sort your standard library actually runs is a battle-tested hybrid of these ideas. Merge, quick, and how libraries really sort.