Recursion

A recursive function calls itself on a smaller input. The description is often shorter than the loop that does the same work, and the cost is a stack frame per call, which is why every recursion needs a base case and a reason to believe the input shrinks.

This lesson writes four working recursions and then produces one that never stops, because the failure mode is part of the technique: the stack has a fixed size, and a recursion without a base case reaches it and crashes.

A base case and a recursive step

factorial(n) is n times factorial(n - 1), and factorial(0) is 1. The first line is the recursive step, the second is the base case, and the base case is what stops the chain: without it the function would call itself with smaller and smaller numbers forever.

Each call waits for the next one to return, so the multiplication happens on the way back. The program prints 120 for 5, and the arithmetic is ordinary int arithmetic, so a large argument would overflow the result long before the stack overflows.

The base case must be reachable. A recursion whose argument does not move towards it is the subject of the last section.

#include <iostream> int factorial(int n) { if (n <= 1) { return 1; } return n * factorial(n - 1); } int main() { std::cout << factorial(5) << '\n'; }

g++ -std=c++23 -Wall -Wextra factorial.cpp -o factorial
./factorial

120

The order of calls and returns

A function can print on the way down and on the way back. The first line of the body runs before the recursive call, the code after it runs when the call returns, so the output shows the descent and then the ascent.

The program counts down to zero and then prints the values on the way back up. That order is the call stack made visible: the last call returns first, and each frame prints its own number before it disappears.

Recursion depth is bounded by the stack, roughly a few thousand frames for a function with a few locals. The explicit limit in the next section keeps the program inside that bound and prints how deep it went.

#include <iostream> void countdown(int n) { std::cout << "enter " << n << '\n'; if (n > 1) { countdown(n - 1); } std::cout << "leave " << n << '\n'; } int main() { countdown(3); }

g++ -std=c++23 -Wall -Wextra unwind.cpp -o unwind
./unwind

enter 3
enter 2
enter 1
leave 1
leave 2
leave 3

Euclid's algorithm

The greatest common divisor of two integers has a recursive definition that shrinks the numbers every time: gcd(a, b) is gcd(b, a % b), and gcd(a, 0) is a. Each step replaces the larger number by a remainder, so the pair gets strictly smaller.

The number of steps is logarithmic, which is why the recursion never comes near the stack limit even for large inputs. gcd(1071, 462) takes three steps and returns 21.

Euclid's algorithm is the standard example of a recursion that is naturally a recursion: the loop version needs a temporary and three assignments, and the recursive one is the definition written down.

#include <iostream> int gcd(int a, int b) { if (b == 0) { return a; } return gcd(b, a % b); } int main() { std::cout << gcd(1071, 462) << '\n'; }

g++ -std=c++23 -Wall -Wextra gcd.cpp -o gcd
./gcd

21

An explicit depth limit

When the depth is bounded by the input, a recursion is safe. When it is not, a limit turns a crash into a result: the function stops at the limit and returns a value that says so.

The program walks a chain of 5 steps and stops at 100, printing how many steps it took. The limit is checked before the recursive call, so the call stack never grows past it.

Production code often does the same with a counter or a visited set, especially for recursive parsers and directory walks, where the input comes from outside and can be malicious.

#include <iostream> int walk(int step, int limit) { if (step >= limit) { return step; } return walk(step + 1, limit); } int main() { std::cout << "steps: " << walk(0, 5) << '\n'; std::cout << "capped: " << walk(0, 100) << '\n'; }

g++ -std=c++23 -Wall -Wextra depth.cpp -o depth
./depth

steps: 5
capped: 100

When the base case is missing

The function below increments a global counter and calls itself, with no base case and no shrinking argument. GCC recognises the shape and warns that the recursion is infinite, then compiles it anyway.

Running it fills the stack until the process hits the guard page and the kernel sends SIGSEGV. GDB catches the signal, and the backtrace shows the same function repeated thousands of times: that repetition is the definition of a stack overflow.

The frame number in the output is the depth this run reached, and it changes with the environment and the stack limit; the addresses change on every run. The fix is a base case, or a loop, which uses one frame instead of thousands.

#include <iostream> int depth = 0; int dive(int n) { ++depth; return dive(n + 1) + 1; } int main() { std::cout << dive(0) << '\n'; }

g++ -g -std=c++23 -Wall -Wextra overflow.cpp -o overflow
gdb -q -batch -ex 'set disable-randomization off' -ex run -ex 'bt 4' ./overflow

overflow.cpp: In function 'int dive(int)':
overflow.cpp:5:5: warning: infinite recursion detected [-Winfinite-recursion]
5 | int dive(int n)
| ^~~~
overflow.cpp:8:16: note: recursive call
8 | return dive(n + 1) + 1;
| ~~~~^~~~~~~

Program received signal SIGSEGV, Segmentation fault.
0x00005c08dedeb19d in dive (n=<error reading variable: Cannot access memory at address 0x7ffe38c39ffc>) at overflow.cpp:6
6 {
#0 0x00005c08dedeb19d in dive (n=<error reading variable: Cannot access memory at address 0x7ffe38c39ffc>) at overflow.cpp:6
#1 0x00005c08dedeb1bc in dive (n=262031) at overflow.cpp:8
#2 0x00005c08dedeb1bc in dive (n=262030) at overflow.cpp:8
#3 0x00005c08dedeb1bc in dive (n=262029) at overflow.cpp:8

Exercises

  1. Write a recursive function that sums the digits of a positive int and test it with 12345 and with 0.
  2. Rewrite factorial as a loop and compare the two versions for n = 20. Which one is easier to read, and which overflows first?
  3. Call walk with a limit of 1000000. What happens, and how would you change the function to survive it?

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What is the base case of a recursion?

    Answer

    The input for which the function returns without calling itself

    Without a case that stops the descent, the calls never end and the stack runs out.

  2. What does each recursive call cost?

    Answer

    A stack frame for the parameters, locals and return address

    The frames accumulate until the base case returns, which is why depth is limited.

  3. This function is called as down(3). In what order do the calls return? void down(int n) { std::cout << "enter " << n << std::endl; if (n > 1) down(n - 1); std::cout << "leave " << n << std::endl; }

    Answer

    The last call returns first

    The stack is last in, first out, so the deepest call finishes before its caller.

  4. Why does the lesson add an explicit depth limit?

    Answer

    A very deep recursion would exhaust the stack

    The limit turns an uncontrolled descent into a defined stop, which the depth program shows.

  5. What does this program print? #include <iostream> int factorial(int value) { return value <= 1 ? 1 : value * factorial(value - 1); } int main() { std::cout << factorial(5); }

    Answer

    120

    The recursion multiplies 5 by 4, 3, 2 and 1, and the base case returns one.

  6. What does this program print? #include <iostream> void down(int n) { std::cout << "enter " << n << '\n'; if (n > 1) down(n - 1); std::cout << "leave " << n << '\n'; } int main() { down(3); }

    Answer

    enter 3 / enter 2 / enter 1 / leave 1 / leave 2 / leave 3

    The calls descend to the base case, and the prints after the call come back in reverse.

  7. What does this program print? #include <iostream> int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } int main() { std::cout << gcd(1071, 462); }

    Answer

    21

    Euclid's algorithm on 1071 and 462 reaches 21, the greatest common divisor.

  8. What does this program print? #include <iostream> int steps(int n, int limit) { if (n <= 0 || limit == 0) return 0; return 1 + steps(n - 1, limit - 1); } int main() { std::cout << "steps: " << steps(5, 100) << " / capped: " << steps(1000, 100); }

    Answer

    steps: 5 / capped: 100

    The uncapped recursion reports its five steps, and the limit stops the second call at 100.

  9. The build command is g++ -std=c++23 -Wall q.cpp. What does the compiler warn about? int dive(int n) { return dive(n + 1) + 1; }

    Answer

    infinite recursion detected

    The function always calls itself, and the warning names the recursion and the call.

  10. This function is called once with dive(1). What happens? int dive(int n) { return dive(n + 1) + 1; }

    Answer

    It receives SIGSEGV when the stack is exhausted

    The frames keep growing until the guard page is touched, and the process dies with SIGSEGV.

The code on this page was built with g++ 15.2.0 and GDB 16.3 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev

Banner image