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. 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.
New to what a function call costs? Start here
Calling a function needs somewhere to keep where to return to, and the arguments, and the local variables. That somewhere is a frame, and frames pile up: the one you are in sits on top of the one that called you.
Nobody declares that memory and nobody frees it explicitly, which is why a function that calls itself can exhaust it. The depth is the cost, and it is invisible in the source.
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.
2 × 4 bytes = 8
- one frame costs
- 20 bytes (4 return address, 4 saved frame pointer, 8 locals)
- the stack holds
- 1,024 bytes
- so it can recurse
- 51 deep
1,024 divided by 20 is 51, and 1,020 of the 1,024 bytes are spent, leaving 4 — 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(56) | 20 bytes | 20 of 1,024 |
| 2 | factorial(55) | 20 bytes | 40 of 1,024 |
| 3 | factorial(54) | 20 bytes | 60 of 1,024 |
| 4 | factorial(53) | 20 bytes | 80 of 1,024 |
| 5 | factorial(52) | 20 bytes | 100 of 1,024 |
| 6 | factorial(51) | 20 bytes | 120 of 1,024 |
| 7 | factorial(50) | 20 bytes | 140 of 1,024 |
| 8 | factorial(49) | 20 bytes | 160 of 1,024 |
| 9 | factorial(48) | 20 bytes | 180 of 1,024 |
| 10 | factorial(47) | 20 bytes | 200 of 1,024 |
| 11 | factorial(46) | 20 bytes | 220 of 1,024 |
| 12 | factorial(45) | 20 bytes | 240 of 1,024 |
It asked for 56 and got 51. The stack ran out at depth 51; 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
- 51
- frames actually pushed
- 51
- agree
- yes
The arithmetic said 51 before anything ran, and the run stopped at 51.
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, 20 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 400 bytes to compute what the loop computes in 1 frame and 20. 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.
| claim | held | measured |
|---|---|---|
| a frame of 20 bytes fits 51 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 51 to 13 | 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 20 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) plus the argument (4) | yes | frameBytes(0) is 12, 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.
The argument was on the table and not in the sum
Every frame in the table prints the argument the recursion is counting down, and until 2026-08-30 the arithmetic charged nothing for it: the depth was computed as though a frame held only a return address, a saved frame pointer and the locals. An outside reader noticed the drawing and the sum disagreeing. Charging four bytes for it moves the default frame from 16 bytes to 20 and the depth from 64 to 51, and both numbers on this page are computed rather than typed, so they moved by themselves. A break-it-on-purpose case now removes the charge again and requires the page to notice.
Sources
- E. W. Dijkstra, Recursive Programming, Numerische Mathematik 2, 1960. The stack and the display that ALGOL 60's recursion required.
- P. Naur (ed.), Revised Report on the Algorithmic Language ALGOL 60, 1963, as text. The language that made recursion something a compiler had to solve. This is the revised report rather than the CACM 3(5) original of 1960, whose DOI is 10.1145/367177.367199 and which resolves to an ACM consent page; the revision is the version anybody reads and the one this page can be checked against.
- Logical Art, the studio this belongs to.