The Stack and Function Calls
Every function call needs somewhere to remember where to come back to, and a private place for its local variables. The call stack is that place: each call pushes a frame onto it and each return pops one off, in strict last-in, first-out order.
A stack trace is a printout of those frames. A stack overflow is running out of room for them. And recursion is a program that leans on them harder than any other, so a correct recursive function can still be crashed by input that is merely deep. This topic follows the frames and prices each of those three.
A Frame per Call
Calling a function pushes a frame that holds the return address, meaning where in the caller execution resumes, along with the arguments, the local variables and any registers the call must preserve. Returning pops the frame and jumps to the saved return address, which in the terms of the previous topic writes it back into the program counter.
Because the most recent call always returns first, a stack is the only bookkeeping needed. The figure shows three calls in progress: main called load_catalogue, which called parse_line. Only the top frame is running. The two below it are paused, each waiting at the line where it made its call, with its locals intact.
Cheap by Construction
In compiled code, pushing a frame means moving one register, the stack pointer, down by the size of the frame, and popping it means moving it back. A call costs a few nanoseconds, and compilers often remove it entirely by copying the function's body into the caller, which is called inlining and belongs to Chapter 13.
CPython does more work per call. It creates a frame for the interpreter, binds the arguments to parameter names, and sets up the new function's local variables. Measured on CPython 3.15, calling a function that returns its argument costs about 30 nanoseconds. A tiny function called a billion times in a loop is where interpreted code loses the most, because the call costs more than anything the function does.
What a Stack Trace Is Made Of
When an exception is raised and not caught, the interpreter walks the frames from the innermost outward, and Python prints them oldest first: the module, then each call down to the line that raised. Here is what CPython 3.15 printed for the three calls in the figure when the second line of input held a malformed number.
Traceback (most recent call last):
File "catalogue.py", line 17, in <module>
main()
File "catalogue.py", line 14, in main
load_catalogue(["17,oak desk", "1x8,pine shelf"])
File "catalogue.py", line 9, in load_catalogue
records.append(parse_line(line))
File "catalogue.py", line 3, in parse_line
return int(fields[0]), fields[1]
ValueError: invalid literal for int() with base 10: '1x8'
Each pair of lines in that trace is one frame on the stack at the moment of the error: the module at line 17, main at line 14, load_catalogue at line 9 and parse_line at line 3, where the conversion to an integer failed on the text "1x8". The trace shows the chain of callers active at that moment, and nothing else. It is not a history of what ran before. A function that returned a wrong value three calls earlier has already popped its frame and does not appear, even if it caused the problem.
Recursion and Its Depth
A recursive function pushes one frame per level. Walking a balanced tree of a million nodes takes about 20 levels. Walking a degenerate tree, a linked chain of 100,000 nodes, or a tree built from sorted input, which Chapter 6 shows, takes 100,000 levels. CPython 3.15 stops Python-level recursion at a limit of 1,000 frames by default: a simple recursive function measured on 3.15 reached a depth of 999 below the calling code and then raised RecursionError, "maximum recursion depth exceeded".
Raising the limit behaves differently on 3.15 than folklore says. Pure Python recursion no longer lives on the native thread stack: with the limit raised to 10 million, a function recursed 2 million levels deep and completed, using about 300 megabytes of memory, roughly 150 bytes per frame. Recursion that passes through code written in C is different. Parsing deeply nested JSON, printing a deeply nested list, or a Python function called back from a C function all consume the native stack, which is fixed in size per thread: commonly 8 megabytes for a program's main thread on Linux and 512 kilobytes for other threads on macOS. On supported platforms CPython now measures how much of that stack it has used and raises RecursionError with the message "Stack overflow" instead of crashing: on 3.15, parsing a JSON array nested a million deep failed that way, while 100,000 levels parsed fine.
Stack Overflow and Deep Input
Most real stack overflows come from deep data, not infinite recursion. A JSON document nested 10,000 levels deep, an expression parser fed a long chain of opening parentheses, which Chapter 13 builds, or a recursive walk of a directory tree that follows a link back to its own parent: each is legitimate recursion, correctly written, that runs out of frames on input shaped to be deep.
Any recursive routine over untrusted input can be crashed by that input. Nesting costs the sender almost nothing, a few bytes per level, and costs the receiver a frame per level. That asymmetry makes it one of the cheapest denial-of-service attacks there is, and it is why well-written parsers carry an explicit depth limit.
The Price of Recursion in Your Code
Python does not remove tail calls, by design, so that every frame appears in tracebacks, and recursion depth is always paid in frames. Converting a recursive walk into a loop that keeps its pending work in a list used as a stack changes the price: depth becomes a heap-memory cost, one 8-byte list slot per pending item, instead of a limit and an exception. The structure is the same last-in, first-out idea, held in a list the program controls, which Chapter 5 covers.
Stacks are also a per-thread cost. Every thread you start reserves its own native stack, so ten thousand threads reserve ten thousand stacks, which is one reason services that handle ten thousand connections use an event loop instead, the subject of Chapter 11.
The call stack, this topic, is the frames of the function calls currently in progress.
Stack memory is the region of memory that holds them, and how allocating there compares with allocating on the heap is the subject of Chapter 4.
A stack data structure is any last-in, first-out container, such as a Python list used with append and pop, covered in Chapter 5. The call stack is one stack data structure, kept in stack memory: three meanings of one word.
- "A stack trace shows what happened before the error." It shows the calls still in progress when the error was raised. A function that returned a wrong value three calls earlier is not in the trace, which is why finding where a bad value came from often needs logging or a debugger.
- "Raising the recursion limit fixes RecursionError." On CPython 3.15 it lets pure Python recursion go deeper at about 150 bytes of memory per frame, and it does nothing for recursion through C code, which still stops at the native stack. Older versions and other interpreters could crash outright. The fix for deep input is iteration.
- "Python optimizes tail recursion." It does not, by design, so that every frame appears in tracebacks. A tail-recursive function over a list of 100,000 items needs 100,000 frames.
- "Stack overflow means infinite recursion." Correct recursion over deep but legitimate input overflows too. A document nested 10,000 levels deep, or a tree built from sorted input, is enough.
- "Function calls are free." In compiled code they are close to free and often inlined away. In CPython each call measured about 30 nanoseconds of setup, which dominates a tight loop over a tiny function.
- Rewrite recursion over data whose depth an outsider controls as a loop with an explicit stack. Depth becomes a memory cost instead of an exception.
- Put a depth limit on every parser and recursive walker that reads untrusted input. Nesting is the cheapest attack there is.
- Read a stack trace as "who called whom to get here", then look outside it for where the bad value came from. The trace lists the path, not the cause.
- Keep hot loops free of tiny function calls in interpreted code when a profile shows call overhead. Inlining by hand is ugly, and sometimes it is the whole cost.
Knowledge Check
Why is a last-in, first-out stack enough to keep track of function calls?
- Every function has the same number of local variables
- Only one function call can be in progress at any time
- The most recent call always returns before its callers
- Functions are always called in alphabetical name order
A traceback ends in parse_line, but the bad value was produced by a helper that load_catalogue called and that returned earlier. Why is the helper missing?
- The helper had returned and its frame was already popped
- Python hides frames from helpers to keep tracebacks short
- The helper was inlined into its caller by the interpreter
- The helper lives in another module, whose frames are separate
A service parses JSON uploads with a recursive routine written in C. A crafted upload nests arrays a million levels deep. What is the fix?
- Raise the recursion limit well above one million
- Move the service to a machine with a faster CPU
- Enforce a depth limit, or use an iterative parser
- Limit uploads to 100 megabytes, and nothing else
A recursive tree walk is rewritten as a loop that pushes pending nodes onto a list. What changes about its cost for a very deep tree?
- The walk becomes O(log n), because the loop skips levels
- It uses no extra memory at all, because loops need none
- It runs a hundred times faster, because loops are compiled
- Depth now costs heap memory instead of frames and a limit
You got correct