Why this matters
A function that calls itself is called a recursive function. Recursion is a natural way to write many algorithms, such as walking a tree or splitting a problem in half. It also has a hard limit that beginners do not see until the program stops. Every call takes some memory, and that memory comes from a fixed-size area. Too many calls, and the program fails.
This lesson shows where that memory comes from, how to measure the limit on your own machine, and what the failure looks like in C++ and in Java. Recursion on linked lists appears in the linked lists module, which names this limit too. The stack and heap lesson earlier in this module introduces the two memory areas, so this lesson uses those words without explaining them again.
You do not need any Java knowledge beyond reading the code. Each Java sample is short and is explained line by line.
The call stack in plain words
When a function calls another function, the computer must remember two things. It must remember where to continue when the inner function returns. It must also keep the local variables of the outer function, because they are still needed. The computer keeps this information in a region of memory called the call stack, or just the stack.
Each call gets its own block of the stack. The block is called a frame. It holds the return address, the arguments and the local variables of that call. When a call starts, a new frame is added on top. When the call returns, its frame is removed. The rule is last in, first out, like a stack of plates: the plate you put on last is the first one you take off.
Here is a small function that calls another function:
#include <cstdio>
int square(int x) {
return x * x;
}
int main() {
int a = 3;
int b = square(a);
std::printf("%d\n", b);
}While square runs, the stack has two frames: the frame for main, which holds a and b, and the frame for square, which holds x. When square returns 9, its frame is removed, and main continues with the frame it still has.
The important point is the size of the stack. It is fixed when the program starts. On Linux, the main thread of a C++ program usually gets a stack of 8 MB by default. You can check the limit with the ulimit command, which prints the stack size in kilobytes:
ulimit -sOn the machine used for this lesson, it printed:
8192That is 8192 kilobytes, which is 8 MB. Each recursive call adds a frame, so a long enough chain of calls uses up all 8 MB.
Recursion uses one frame per call
Here is a recursive function that adds the numbers from 1 to n:
long long sum_to(long long n) {
if (n == 0) return 0; // base case: stop here
return n + sum_to(n - 1); // the call waits for the answer below it
}Trace sum_to(3) by hand. The call sum_to(3) cannot finish until sum_to(2) gives an answer. That call waits for sum_to(1), which waits for sum_to(0). The call sum_to(0) returns 0 without making another call. Then the waiting calls finish in reverse order:
sum_to(3) waits for sum_to(2)
sum_to(2) waits for sum_to(1)
sum_to(1) waits for sum_to(0)
sum_to(0) returns 0
sum_to(1) returns 1 + 0 = 1
sum_to(2) returns 2 + 1 = 3
sum_to(3) returns 3 + 3 = 6At the deepest point, four frames are on the stack at once: one for each of sum_to(3), sum_to(2), sum_to(1) and sum_to(0). For sum_to(1000000), a million frames would be on the stack at the same time. The if (n == 0) line is the base case. It is the only place where the calls stop going deeper. Without it, the chain never ends.
Watching the frames move
A frame has an address like any other memory. The program below prints the address of a local variable in each call. The address of each call's variable moves by the size of one frame, so the difference between two lines shows the frame size.
#include <cstdint>
#include <cstdio>
// Prints where each call keeps its local variable.
void show(int depth, std::uintptr_t previous) {
int local = depth;
auto here = reinterpret_cast<std::uintptr_t>(&local);
if (depth > 0) {
std::printf("depth %d: local at %#lx, moved %ld bytes from the previous call\n",
depth, static_cast<unsigned long>(here),
static_cast<long>(previous) - static_cast<long>(here));
} else {
std::printf("depth %d: local at %#lx\n", depth, static_cast<unsigned long>(here));
}
if (depth < 4) show(depth + 1, here);
}
int main() {
show(0, 0);
}The reinterpret_cast line converts the address of local into a plain number, so it can be printed.
Compile it without optimization, so the variable really lives in the frame:
g++ -std=c++20 -Wall -O0 frames.cpp -o frames
./framesThe output was:
depth 0: local at 0x7ffc86c8623c
depth 1: local at 0x7ffc86c861fc, moved 64 bytes from the previous call
depth 2: local at 0x7ffc86c861bc, moved 64 bytes from the previous call
depth 3: local at 0x7ffc86c8617c, moved 64 bytes from the previous call
depth 4: local at 0x7ffc86c8613c, moved 64 bytes from the previous callThe addresses will be different on your run, because the operating system places the stack at a random position for safety. The differences are the part to notice. Each call moves the address down by 64 bytes, so the stack grows toward lower addresses. This function's frame is 64 bytes at this setting. It is larger than the frame of sum_to in the next section, which the measurement there puts at about 32 bytes.
Measuring the limit
The frame size is not the same for every function. A simple function like sum_to has a small frame, so it can go deeper than show. The only reliable way to find the limit is to measure it. The program below calls sum_to with a number given on the command line. If the program finishes, its exit code, the number it hands back to the shell, is 0. If the stack runs out, the operating system stops the program with a segmentation fault, and the shell reports exit code 139.
#include <cstdio>
#include <cstdlib>
long long sum_to(long long n) {
if (n == 0) return 0;
return n + sum_to(n - 1);
}
int main(int argc, char** argv) {
long long n = std::atoll(argv[1]);
std::printf("sum_to(%lld) = %lld\n", n, sum_to(n));
}Build it without optimization, then try a few sizes:
g++ -std=c++20 -Wall -O0 depth.cpp -o depth
./depth 10000
./depth 100000
./depth 1000000
echo "exit=$?"The first two runs printed the sum and exited with 0. The third run printed nothing and the shell reported a crash. The exit code of the last run was 139.
The exact limit is found by testing a range of sizes. A binary search keeps the test short: it tries the midpoint, keeps the half that passes, and repeats. The shell loop below does that between 100,000 and 1,000,000. It uses only the exit code, so it needs no output parsing.
lo=100000; hi=1000000
while [ $((hi - lo)) -gt 1000 ]; do
mid=$(((lo + hi) / 2))
if ./depth $mid >/dev/null 2>&1; then lo=$mid; else hi=$mid; fi
done
echo "largest passing n is about $lo, first failing n is about $hi"On the test machine, with the default 8 MB stack, the output was:
largest passing n is about 260839, first failing n is about 261718So sum_to can make about 261,000 nested calls before the program crashes. Dividing 8 MB by 261,000 calls gives about 32 bytes per frame for this function at this optimization level. Your number will differ, because the frame size depends on the compiler, the flags, the processor and the operating system.
Raising the limit
The limit can be raised for one shell. The command below sets the stack to 64 MB for the program started in that subshell, and it only works because the hard limit on this machine is unlimited:
( ulimit -s 65536; ./depth 1000000 ; echo "exit=$?" )
( ulimit -s 65536; ./depth 3000000 ; echo "exit=$?" )The first run with 1,000,000 calls passed. The run with 3,000,000 calls crashed. A bigger stack moves the wall further away, but it does not remove it. A function that never stops calling itself will crash with any stack size.
What the crash looks like in C++
A C++ program that overflows the stack is stopped by the operating system with a segmentation fault. A segmentation fault means the program touched memory it was not allowed to touch. The stack overflow is one case of this, because the next frame would lie beyond the reserved stack area.
Running the crashing command in bash printed this line from the shell:
bash: line 1: 764686 Segmentation fault ./depth 1000000 > /dev/null 2> err2.txtThe number is the process ID, which changes each time. The important parts are the words Segmentation fault and the exit code 139. The C++ code cannot catch this with try and catch, because the operating system ends the process before any C++ code runs. A C++ program has no standard way to recover from a stack overflow.
The AddressSanitizer message
A sanitizer is a compiler feature that checks a program while it runs and reports certain bugs with a clear message. AddressSanitizer, enabled with -fsanitize=address, can name a stack overflow directly. It needs the -g flag so that it can print line numbers.
g++ -std=c++20 -Wall -g -fsanitize=address sumto.cpp -o sumto_asan
./sumto_asan 1000000The start of its output was:
AddressSanitizer:DEADLYSIGNAL
=================================================================
==892469==ERROR: AddressSanitizer: stack-overflow on address 0x7fff6d65aff8 (pc 0x5f44cb2d2215 bp 0x7fff6d65b000 sp 0x7fff6d65aff0 T0)
#0 0x5f44cb2d2215 in sum_to(long long) .../sumto.cpp:4
#1 0x5f44cb2d2236 in sum_to(long long) .../sumto.cpp:6
#2 0x5f44cb2d2236 in sum_to(long long) .../sumto.cpp:6
#3 0x5f44cb2d2236 in sum_to(long long) .../sumto.cpp:6
#4 0x5f44cb2d2236 in sum_to(long long) .../sumto.cpp:6The frame lines show the chain of calls. Most point at line 6 of sumto.cpp, the recursive call in sum_to. The top frame, #0, points at line 4, the line that opens the function, where the new frame is set up. The full path is shortened here with ..., and the addresses and process ID change on each run. The line stack-overflow names the problem. A sanitizer build is slower, so use it for debugging, not for measurement.
What the crash looks like in Java
Java handles this differently. The Java virtual machine, which runs Java programs, gives each thread a stack of a fixed size. When a thread runs out of stack, the virtual machine throws an error called StackOverflowError. Java code can catch that error, just as it catches an exception. Java classes it as an Error, which means a serious problem that programs are not expected to handle, rather than an Exception.
The program below prints how many calls it made before the error. The counter is a static field, which means the whole class shares one copy of it.
public class StackDepth {
static long depth = 0;
static long sumTo(long n) {
depth++;
if (n == 0) return 0;
return n + sumTo(n - 1);
}
public static void main(String[] args) {
long n = Long.parseLong(args[0]);
try {
System.out.println("sumTo(" + n + ") = " + sumTo(n));
} catch (StackOverflowError e) {
System.out.println("StackOverflowError after about " + depth + " calls");
}
}
}The try block runs the recursive call. If the stack runs out, the catch block handles the error and prints the count. Compile and run it:
javac -Xlint:all StackDepth.java
java -cp . StackDepth 1000
java -cp . StackDepth 10000000The first run printed sumTo(1000) = 500500, because 1000 calls fit easily. The second run printed:
StackOverflowError after about 10839 callsRepeated runs gave counts such as 10842, 10748 and 11028. The count changes between runs, for a reason covered in the mistakes section below. On the test machine, Java's default thread stack size is 1024 KB, which the command java -XX:+PrintFlagsFinal -version reports as ThreadStackSize = 1024. So a Java recursive call uses about 100 bytes of stack in this test.
The size can be changed with the -Xss option, which sets the stack size per thread:
java -Xss256k -cp . StackDepth 100000
java -Xss4m -cp . StackDepth 10000000The first command printed StackOverflowError after about 1316 calls. The second printed StackOverflowError after about 99487 calls. A smaller stack gave fewer calls, and a bigger stack gave more. The counts were not stable, though: later runs with -Xss4m gave anywhere from about 50,000 to 115,000 calls. The likely cause is the compiler change described in the mistakes section, so do not predict Java depths by simple division.
An uncaught Java overflow
When nothing catches the error, Java prints a stack trace and stops the program. This small program has no try block:
public class Forever {
static int countdown(int n) {
return countdown(n - 1) + 1;
}
public static void main(String[] args) {
System.out.println(countdown(3));
}
}Running it printed these first lines:
Exception in thread "main" java.lang.StackOverflowError
at Forever.countdown(Forever.java:3)
at Forever.countdown(Forever.java:3)
at Forever.countdown(Forever.java:3)The output stops after 1,024 frame lines, which is the default limit on the frames Java prints. The first line names the error. Each at line is one frame, and the number in brackets is the line in the source file. Java prints the frames from the innermost call outward, so the top line is the call that failed. The program has no base case, so every call makes another call.
Worked example: big local variables use the stack too
The size of a frame includes every local variable. A local array of 100 KB inside a recursive function takes 100 KB per call, and the stack limit is reached after far fewer calls. The next program makes this easy to see. It has two versions of the same function. One keeps a 100 KB array on the stack. The other keeps the same array in a std::vector, which stores its items on the heap, and the stack only holds a small handle to it.
#include <array>
#include <cstdio>
#include <cstdlib>
#include <vector>
// Each call keeps a 100 KB array on the stack.
int count_on_stack(int n) {
std::array<char, 100'000> buffer{};
buffer[0] = 1;
if (n == 0) return 0;
return count_on_stack(n - 1) + buffer[0];
}
// Same work, but the 100 KB lives on the heap. The stack only holds a pointer.
int count_on_heap(int n) {
std::vector<char> buffer(100'000);
buffer[0] = 1;
if (n == 0) return 0;
return count_on_heap(n - 1) + buffer[0];
}
int main(int argc, char** argv) {
int n = std::atoi(argv[1]);
if (argv[2][0] == 's') std::printf("stack version counted %d\n", count_on_stack(n));
else std::printf("heap version counted %d\n", count_on_heap(n));
}The first argument is the depth. The second argument is s for the stack version or anything else for the heap version. Each function returns the depth it was given, so the output can be checked by hand.
g++ -std=c++20 -Wall -O0 bigframe.cpp -o bigframe
./bigframe 80 s
./bigframe 82 s
./bigframe 83 s
echo "exit=$?"The first two commands printed stack version counted 80 and stack version counted 82. The third command printed nothing and crashed. The stack version works up to 82 and fails at 83. Each level holds a little over 100,000 bytes, so 83 levels need about 8.4 MB, which is more than the 8 MB stack (8,388,608 bytes).
The heap version reaches a much larger depth:
./bigframe 50000 hIt printed heap version counted 50000. A search like the one shown earlier found that the heap version passes up to about 87,133 levels and fails at 87,207. That limit is set by the small frame of the function itself, about 96 bytes per call, and not by the 100 KB buffer. The buffer is on the heap, so its size no longer matters for the stack.
Worked example: optimization can remove the calls
Some recursive calls do not need a new frame at all. A tail call is a call that is the last thing a function does, and whose result is returned directly. The compiler can turn such a call into a jump back to the start of the function, which reuses the same frame. The program below uses a tail call.
#include <cstdio>
#include <cstdlib>
// The last thing this function does is call itself, so it is a tail call.
long long count_up(long long n, long long acc) {
if (n == 0) return acc;
return count_up(n - 1, acc + 1);
}
int main(int argc, char** argv) {
long long n = std::atoll(argv[1]);
std::printf("count_up(%lld) = %lld\n", n, count_up(n, 0));
}Build it twice, once with -O0 and once with -O2:
g++ -std=c++20 -Wall -O0 tail.cpp -o tail0
g++ -std=c++20 -Wall -O2 tail.cpp -o tail2
bash -c './tail0 10000000; echo "O0 exit=$?"'
bash -c './tail2 10000000; echo "O2 exit=$?"'
bash -c './tail2 1000000000000; echo "O2 huge exit=$?"'The -O0 build crashed on 10,000,000 calls, with exit code 139. The -O2 build printed count_up(10000000) = 10000000, with exit code 0, and it handled 1,000,000,000,000 calls the same way. At -O2, the compiler turned the recursion into a loop, so no new frames were made.
This does not mean the program is safe. The optimization is the compiler's choice, and it depends on the flags, the compiler version and the code around the call. Code that depends on it can crash when built differently. A recursive call that is not a tail call, such as n + sum_to(n - 1) above, cannot be turned into a loop this way, because the addition must happen after the inner call returns.
Common mistakes
A missing base case
The most common cause of a stack overflow is a recursive function with no stopping case. The program below has no base case:
#include <cstdio>
int countdown(int n) {
std::printf("%d\n", n);
return countdown(n - 1);
}
int main() {
return countdown(3);
}Compiling it with -Wall gave this warning:
forever.cpp: In function 'int countdown(int)':
forever.cpp:3:5: warning: infinite recursion detected [-Winfinite-recursion]
3 | int countdown(int n) {
| ^~~~~~~~~
forever.cpp:5:21: note: recursive call
5 | return countdown(n - 1);
| ~~~~~~~~~^~~~~~~The compiler spotted that the function always calls itself. Running the program printed 3, 2, and many more numbers, then the shell reported Segmentation fault with exit code 139. Read every warning from the compiler before running a recursive function for the first time.
Assuming one limit for every function
A function with a 100 KB local array failed at 83 levels of recursion. A function with one long long parameter reached about 261,000 levels. Neither number is a rule. Before you trust a recursion depth, measure the function you wrote, with the flags you will use.
A practical check is to ask how many bytes each call needs and multiply by the depth. For sum_to at 32 bytes per frame, 100,000 levels need about 3.2 MB, which fits in 8 MB. For the 100 KB version, 100 levels need 10 MB, which does not.
Raising the limit instead of fixing the recursion
Increasing the stack with ulimit -s or -Xss is sometimes useful, but it only moves the point of failure. A recursion with no base case still crashes, just later. Fix the base case first, and change the limit only when the depth is known and needed.
Catching StackOverflowError to hide a bug
Java lets the program catch StackOverflowError, but catching it does not repair the work that failed. The catch block in the sample printed a count and ended the method. If the program carried on as if the sum had succeeded, it would use a wrong answer. Catch the error only when the program has a clear plan for what to do next, such as switching to a loop.
Forgetting that the count changes
The Java counts differed between runs: 10,839, 10,842, 10,748 and 11,028 calls. The Java virtual machine compiles frequently used code to machine code while the program runs. The likely cause is that interpreted code and compiled code use frames of different sizes, so the depth reached before the error depends on when the compiler finished its work. Do not treat a single count as exact.
Practice
Exercise 1: Estimate the depth
A recursive C++ function uses a 32-byte frame. The default stack is 8 MB. Estimate how many levels it can reach before a stack overflow, and say whether 100,000 levels fit.
Show the answer
8 MB is 8,388,608 bytes. Dividing by 32 bytes per frame gives about 262,000 levels. The measured value for sum_to was about 261,000, which is close. So 100,000 levels, which need about 3.2 MB, fit in the stack.
Exercise 2: Write a recursive length
Write a recursive function int length(const Node* head) for a linked list, where each node has an int value and a Node* next. It must return the number of nodes, and it must stop at nullptr.
Show the answer
int length(const Node* head) {
if (head == nullptr) return 0;
return 1 + length(head->next);
}The base case is head == nullptr, which is the end of the list. Each call adds 1 and asks about the rest of the list. A list with 100,000 nodes makes 100,000 nested calls. In a test at -O0, length returned 100,000 and 200,000 without a crash, and it crashed at 300,000 nodes. The exact limit depends on the machine, so a list of a million nodes should be walked with a loop.
Exercise 3: Turn the recursion into a loop
Rewrite the function below as a loop, so that its depth does not depend on the stack size.
long long sum_to(long long n) {
if (n == 0) return 0;
return n + sum_to(n - 1);
}Show the answer
long long sum_to(long long n) {
long long total = 0;
for (long long i = 1; i <= n; ++i) total += i;
return total;
}The loop uses one frame in total, no matter how large n is. The sum is the same. The loop version does not wait for inner calls, so there is no chain of pending work for the stack to hold.
Exercise 4: Predict the crash
A function void visit(int depth) calls itself with depth + 1 and has no base case. Without running anything, predict what happens in C++ at -O0 and in Java. Then say what a -Wall compile would print.
Show the answer
In C++ at -O0, the program runs until the 8 MB stack is full, then the operating system stops it with a segmentation fault and exit code 139. With -Wall, g++ prints the warning infinite recursion detected. In Java, the virtual machine throws StackOverflowError. If nothing catches it, Java prints Exception in thread "main" java.lang.StackOverflowError followed by a stack trace.
Exercise 5: Check a raised limit
The command ( ulimit -s 16384; ./depth 1000000 ) is run in a shell where the hard limit is unlimited. Say what the command sets, and whether the change affects other shells.
Show the answer
The command sets the soft stack limit to 16384 KB, which is 16 MB, for the subshell in the parentheses and for the program it starts. The parent shell keeps its own limit, so other shells are not affected. The change works here only because the hard limit is unlimited. If the hard limit were 8 MB, the increase would fail.
Summary
- Each call uses one frame on the call stack, and the stack has a fixed size, usually 8 MB for a C++ program on Linux.
- The number of calls before a crash depends on the size of each frame, which depends on the function's locals and on the compiler settings.
- A C++ stack overflow stops the program with a segmentation fault and exit code 139, and the program cannot catch it.
- Java throws
StackOverflowError, which a program can catch, and prints a stack trace when nothing catches it. - Every recursive function needs a base case, and a loop is safer when the depth can be large.