1960

The Call Stack

A function that calls itself allocates memory nobody wrote a line to allocate. Each call leaves a frame behind — a return address, a saved frame pointer, and room for its own locals — and they stack up until there is no room for the next one. The depth at which that happens is not something you discover by crashing: it is frame size times depth against a limit, and this page computes it before running the recursion to exactly that depth.

Frames you did not write down, against a limit you did not set

1 One function that calls itself, and the frame it leaves behind each time

One function calling itself, and what each call leaves behind.

locals per frame2 × 4 bytes = 8

one frame costs: 16 bytes (4 return address, 4 saved frame pointer, 8 locals)
the stack holds: 1,024 bytes
so it can recurse: 64 deep

1,024 divided by 16 is 64, and 1,024 of the 1,024 bytes are spent, leaving 0 — not enough for another frame.

2 Every frame on the stack at once, with what each one is holding

Every frame on the stack at the deepest moment, and what each one is holding.

depth	argument	frame	used
1	factorial(69)	16 bytes	16 of 1,024
2	factorial(68)	16 bytes	32 of 1,024
3	factorial(67)	16 bytes	48 of 1,024
4	factorial(66)	16 bytes	64 of 1,024
5	factorial(65)	16 bytes	80 of 1,024
6	factorial(64)	16 bytes	96 of 1,024
7	factorial(63)	16 bytes	112 of 1,024
8	factorial(62)	16 bytes	128 of 1,024
9	factorial(61)	16 bytes	144 of 1,024
10	factorial(60)	16 bytes	160 of 1,024
11	factorial(59)	16 bytes	176 of 1,024
12	factorial(58)	16 bytes	192 of 1,024

It asked for 69 and got 64. The stack ran out at depth 64; the first twelve are shown.

3 Frame size times depth against a fixed limit, which is where it dies

The arithmetic, then the run. They have to agree, or one of them is wrong.

predicted depth: 64
frames actually pushed: 64
agree: yes

The arithmetic said 64 before anything ran, and the run stopped at 64.

4 The same computation written as a loop, holding one frame forever

The same computation written as a loop. One frame, whatever n is.

loop frames: 1 frame, 16 bytes, whatever n is
loop result at n = 20: 2,432,902,008,176,640,000
recursion agrees: yes, exactly

The recursion needs 20 frames and 320 bytes to compute what the loop computes in 1 frame and 16. Both answers are the same number; only the memory differs.

These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.

Each claim, whether it held, and the values behind it
claim	held	measured
a frame of 16 bytes fits 64 times in 1024, and the recursion stops at exactly that	yes	the depth was computed before it was run, and the run agreed
give each frame 16 locals instead of 2 and the depth falls from 64 to 14	yes	the limit is bytes, not calls, which is why the same program recurses to different depths in different languages
the same computation written as a loop holds one frame at any n	yes	one frame of 16 bytes, and 20! computed inside it
and it gets the same answer as the recursion at n = 5, 10, 15 and 20	yes	20! is 2.4329e+18
a frame with no locals is exactly the return address (4) plus the saved frame pointer (4)	yes	frameBytes(0) is 8, and each local adds 4 bytes
every frame's running total is its depth times its size	yes	no total is stored, only derived

What is real here, and what is not

The limit is modelled and is not your platform's

A thousand and twenty-four bytes is a number this page chose so the arithmetic fits on a screen. A real stack limit is set by the operating system or the runtime and is typically megabytes, and some runtimes grow the stack instead of failing. What is real here is the shape — bytes divided by frame size — and the shape is the subject.

A frame is not eight bytes plus locals on any real machine

Real frames carry saved registers, alignment padding, spilled temporaries and sometimes a canary, and an optimising compiler may remove the frame altogether by turning the recursion into a loop. The two words modelled here are the return address and the saved frame pointer. This page used to say they were “the two every calling convention has”, which is not true and was pointed out by an outside reader: the System V x86-64 ABI explicitly permits omitting the frame pointer, and AArch64 holds the return address in a link register rather than pushing it. Both are common. They are two plausible words, chosen because the arithmetic needs a frame size and these are the ones a reader will recognise, and the page counts nothing else.

Tail calls are the reason this is not always true, and are not modelled

A call in tail position can reuse the frame it is standing in, which makes some recursions cost one frame rather than n. Scheme requires this; C compilers often do it; JavaScript engines mostly do not, despite the specification. The factorial here is not in tail position, so it would not benefit, but a page that did not say this would be implying a rule with a large exception.

Sources

Logical Art builds interactive explanations of difficult machines.

The machines:

1935-1991 RangekeeperThe answer is on both sides of the equation, so it had to be a machine.
1964-1990s AbendThe loop you did not write, and the day it cost to get it wrong.
1971-1995 Line ModeYou could telnet to port 80 and be the browser, and then you could not.
1975 Front PanelA working 1975 Altair 8800 you program by flipping switches.
1980s 300 BaudA real dial-up modem and the BBS on the other end of it.
1994 WinsockThe two seconds after the modem stopped screeching, before anything worked.
2020s LLM LabTrain a tiny language model and watch every number as it learns.

Smaller pieces, on the studio itself: Morse, Baudot, Flip-Flop, Punch Cards, Interlace, Bitwise, The Adder, Stored Program, Two's Complement, Trigger, Bit, Nibble, Byte, Transistor, The Middle Square, Score Reel, Hamming, Huffman, Core Memory, Hash Table, The Interrupt, CORDIC, The Call Stack, Garbage, CRC, The Pipeline, Round Robin, Page Fault, Context Switch, ASCII, The Shuffle, Packet Switching, Bresenham, CPU Cache, Deadlock, Race, Fifteen Planes, B-tree, Bloom Filter, Double Buffer, Avalanche, Backoff, Checkout, Sequence Numbers, Compare and Swap, Diffie-Hellman, Dithering, Zero Address, Fringes, LZ77, Signature, Logical Clock, Z-Characters, Merkle Proof, Branch Prediction, Write-Ahead Log, Interleave, Eight Sprites, DNS, LZW, Floating Point, Slow Start, RAID Parity, Longest Chain, JPEG, UTF-8, Masking, PageRank, AES, Merge Collapse, Merkle DAG, Count Distinct, Majority.

A Logical Art machine by RoamingPigs, Inc. Built by Cisco Caceres in Las Vegas, NV.