C++ / FUNCTIONS
Recursion and stack depth limits
Reason about recursion as live stack frames, estimate how deep your stack can go, and bound or rewrite recursions that would overflow it.
What you will learn
- Count live frames, not total calls: only unfinished calls occupy stack space.
- Estimate the depth ceiling as thread stack size divided by frame size.
- Recognise that stack overflow kills the process instead of raising an exception.
- Rewrite unbounded-depth recursion as a loop over an explicit heap worklist.
Understanding Recursion and stack depth limits
A recursive call is an ordinary call, so it gets an ordinary activation record: space for its parameters, its locals, the address to resume at, and whatever registers the compiler must save. Nothing is shared between levels, so sum_to(4) and sum_to(3) each own a distinct n, and a caller cannot release its frame while it still has work queued for after the call returns. What limits recursion is therefore the number of frames alive at the same moment, not the total number of calls made: a loop that calls a function a billion times keeps one frame live, while a recursion a million deep keeps a million.
The stack is a fixed-size region handed to a thread when it starts and it cannot grow on demand: commonly 8 MiB for the main thread on Linux, 1 MiB on Windows, sometimes a few kilobytes on a microcontroller. Divide that by the size of one frame and you have the depth at which the program stops working, which is why one fat local array inside a recursive function can turn a usable depth of a hundred thousand into two thousand. Running off the end is undefined behaviour rather than a reportable error: in practice the thread touches a guard page and dies with SIGSEGV, and where there is no guard page it quietly overwrites whatever memory lies beyond.
There are three honest ways to stay inside that budget: make the depth logarithmic in the input (recurse into the smaller quicksort partition and loop on the larger one), cap it deliberately with a depth parameter when the shape of the input comes from outside your program, or abandon the call stack and keep pending work in a std::vector you push and pop yourself. Tail recursion is not a fourth way, because C++ requires no tail-call elimination: gcc and clang usually turn a self tail call into a jump at -O2, the same source recurses for real at -O0, and a local with a destructor still pending at the call site means the call was never in tail position at all.
<iostream>
// Each call keeps its own n and its own resume point alive until the call
// it made finishes, so n+1 frames exist at the deepest moment.
long long sum_to(int n, int depth) {
std::cout << "enter n=" << n << " live frames=" << depth << '\n';
if (n == 0) {
std::cout << "base case, deepest point\n";
return 0;
}
long long rest = sum_to(n - 1, depth + 1); // this frame waits here
std::cout << "leave n=" << n << " rest=" << rest << '\n';
return n + rest; // work left to do after the call
}
int main() {
long long total = sum_to(4, 1);
std::cout << "total=" << total << '\n';
}
Recursion depth is a memory budget: every call that has not returned yet owns a stack frame, and stack size divided by frame size is where the program crashes.
Worked examples
Frame size sets the depth limit
Two recursions with the same shape reach very different depths because one carries a 4 KiB local array in every frame.
<iostream>
long long light(int n) { // frame: n, a return address, little else
if (n == 0) return 0;
return n + light(n - 1);
}
long long heavy(int n) {
char scratch[4096] = {}; // 4 KiB of locals in every frame
scratch[0] = 1;
if (n == 0) return scratch[0];
return scratch[0] + heavy(n - 1);
}
int main() {
std::cout << "light(1000) = " << light(1000) << '\n';
std::cout << "heavy(200) = " << heavy(200) << '\n';
std::cout << "heavy(200) reserved " << 201.0 * 4096 / (1024 * 1024)
<< " MiB of scratch arrays\n";
std::cout << "8 MiB / 4096 B = " << (8 * 1024 * 1024) / 4096
<< " heavy frames at most\n";
}
Example explained
Line 1char scratch[4096] lives inside heavy's frame, so one level of heavy costs at least 4 KiB while one level of light costs a few machine words.
Line 2Both functions add something after the recursive call returns, so no frame can be released early: at the deepest point 201 heavy frames are live together.
Line 3Dividing a typical 8 MiB stack by the frame size gives the practical ceiling, roughly 2048 levels of heavy against hundreds of thousands of levels of light.
Line 4The figure is only an estimate because the compiler owns the real layout: at -O2 it may keep light's n in a register and delete heavy's unused array bytes entirely.
Trade the call stack for a heap worklist
Walking a 200000-node chain with an explicit vector of pending items keeps the C++ call stack one frame deep.
<iostream>
<vector>
struct Node { int value; int next; }; // next == -1 marks the end
int main() {
const int depth = 200000;
std::vector<Node> nodes(depth);
for (int i = 0; i < depth; ++i)
nodes[i] = Node{ i + 1, (i + 1 < depth) ? i + 1 : -1 };
std::vector<int> pending; // the stack we control, on the heap
pending.push_back(0);
long long total = 0;
while (!pending.empty()) {
int i = pending.back();
pending.pop_back(); // what "return" would have done for us
total += nodes[i].value;
if (nodes[i].next != -1) pending.push_back(nodes[i].next);
}
std::cout << "visited " << depth << " nodes, sum = " << total << '\n';
}
Example explained
Line 1A recursive walk of this chain would need 200000 live frames; the loop needs one, because the pending indices sit in a heap-allocated vector instead.
Line 2pending.pop_back() is the explicit form of returning from a call: it retires the current item before its successor is queued.
Line 3The heap can serve requests far larger than a thread stack and reports failure by throwing std::bad_alloc, which you can actually catch.
Line 4total must be long long: 200000 * 200001 / 2 is 20000100000, well past the range of a 32-bit int.
Important notes
Frame size is the compiler's decision, not the language's: -O2 can keep locals in registers, inline a level away, or reuse a frame for a tail call, so identical source can crash at very different depths in debug and release builds.
A running thread cannot enlarge its own stack; the size is fixed before the thread starts by a linker option, ulimit, or pthread attribute, so treat it as a hard constant when planning depth.
Common mistakes
Testing only tiny inputs: sum_to(10) proves nothing about sum_to(1000000), which dies with SIGSEGV and a truncated stack trace that points nowhere useful.
Expecting try/catch to help: stack overflow arrives as a fault, not a C++ exception, so catch (...) around the recursive call never runs and the process still dies.
Adding a large local buffer such as char buf[65536] inside the recursive function: the safe depth collapses by orders of magnitude while the algorithm looks unchanged.
Try it yourself
Change, predict, then run
Change sum_to so it also prints the address of a local variable at each level, run it with n = 5, and subtract consecutive addresses to measure the real frame size in bytes. Divide 8388608 by that number to predict the depth at which the function would crash, then test the prediction.
Open the C++ workspaceCheck your understanding
A tail-recursive function that walks a 1,000,000-element list runs fine in your release build but crashes in the debug build. What is the most likely reason?
- The release build turned the self tail call into a jump that reuses one frame, while the debug build pushes 1,000,000 real frames and exhausts the stack.
- Debug builds are given a smaller stack than release builds, so the same frames no longer fit.
- The debug build checks for stack overflow and reports it, while the release build silently ignores the overflow and keeps working.
- Tail recursion is guaranteed constant stack by the C++ standard, so the crash must come from an unrelated bug in the debug-only code.
Show answer
Tail-call elimination is an optimisation, not a language rule: gcc and clang apply it from -O1 upward, while -O0 emits a genuine call per level, so a million frames are live at once and the guard page is hit. Option 1 is tempting but wrong, because the stack limit is set per thread by the OS and linker and is identical in both builds; what changed is how many frames the code creates, not how much room it has.