Recursion and the call stack in C++

A function that keeps 1 KB of local data could call itself 7,579 levels deep on the Mac that ran this lesson’s examples, and one level more crashed the program: the main thread’s stack holds 8,372,224 bytes. A recursive function calls itself to solve a smaller version of its own problem, and each call still waiting for its answer occupies a frame of stack memory, so the deeper it goes, the more stack it uses.

You will write recursive functions whose base case every input reaches, trace their frames as they are pushed and popped, measure the depth limit and read AddressSanitizer’s report past it, see why a tail call is not guaranteed to save a frame, and stop repeated work with memoisation. Every program was built with Apple clang 21 and GCC 16.

A recursive function solves a smaller case of its own problem

A recursive functionrecursive function: A function that calls itself, directly or through other functions, to solve a smaller case of its own problem, such as factorial(n) calling factorial(n - 1). It needs a base case that every input reaches. calls itself: factorial(4) is 4 * factorial(3). Here are three recursive functions that print every call, indented by how deep the call is:

// trace.cpp: three recursive functions that print each call, indented by its depth.
#include <cstdint>
#include <print>
#include <string>

std::string indent(int depth) { return std::string(2 * depth, ' '); }

std::int64_t factorial(int n, int depth = 0) {
    std::println("{}factorial({})", indent(depth), n);
    if (n <= 1) {  // the base case: answered without another call
        std::println("{}factorial({}) returns 1, the base case", indent(depth), n);
        return 1;
    }
    // the recursive case: a smaller problem
    std::int64_t result = n * factorial(n - 1, depth + 1);
    std::println("{}factorial({}) returns {}", indent(depth), n, result);
    return result;
}

// x to the power n in about log2(n) calls: x^n = (x^(n/2))^2, times x again if n is odd.
std::int64_t power(std::int64_t x, int n, int depth = 0) {
    if (n == 0) {
        std::println("{}power({}, 0) returns 1, the base case", indent(depth), x);
        return 1;
    }
    std::println("{}power({}, {})", indent(depth), x, n);
    std::int64_t half = power(x, n / 2, depth + 1);
    std::int64_t result = n % 2 == 0 ? half * half : half * half * x;
    std::println("{}power({}, {}) returns {}", indent(depth), x, n, result);
    return result;
}

// Moves n discs between pegs, never a larger disc on a smaller one; returns the moves.
int hanoi(int n, char from, char to, char spare) {
    if (n == 0) return 0;
    int moves = hanoi(n - 1, from, spare, to);
    std::println("move disc {} from {} to {}", n, from, to);
    return moves + 1 + hanoi(n - 1, spare, to, from);
}

int main() {
    factorial(4);
    power(2, 10);
    std::println("{} moves", hanoi(3, 'A', 'C', 'B'));
}

factorial(4)
  factorial(3)
    factorial(2)
      factorial(1)
      factorial(1) returns 1, the base case
    factorial(2) returns 2
  factorial(3) returns 6
factorial(4) returns 24
power(2, 10)
  power(2, 5)
    power(2, 2)
      power(2, 1)
        power(2, 0) returns 1, the base case
      power(2, 1) returns 2
    power(2, 2) returns 4
  power(2, 5) returns 32
power(2, 10) returns 1024
move disc 1 from A to C
move disc 2 from A to B
move disc 1 from C to B
move disc 3 from A to C
move disc 1 from B to A
move disc 2 from B to C
move disc 1 from A to C
7 moves

Each function has the same two parts. The base casebase case: The input a recursive function answers without calling itself, such as factorial(1), which is 1. Every chain of recursive calls must reach one, or the calls go on until the stack overflows. answers directly: factorial(1) is 1, power(x, 0) is 1, and moving zero discs takes no moves. The recursive case reduces the problem and trusts the function to solve the smaller version: factorial(n) multiplies n by factorial(n - 1). The GCC build printed the same lines. Step through factorial(4) and watch the frames pile up and come off again:

factorial(4) cannot finish until factorial(3) has finished, which waits for factorial(2), and so on down to the base case. Each waiting call keeps a stack framestack frame: The block of the call stack that belongs to one call that has not returned yet: its parameters, its local variables, saved registers and the address to return to. A call pushes it and the return pops it. with its own n, which is why each one remembers what to multiply by when the answer comes back. The results then return in the reverse order: 1, 2, 6, 24.

The trace also shows how deep each function goes. factorial(n) is n calls deep. power(2, 10) halves its exponent on every call, so it is only five calls deep (10, 5, 2, 1, 0): halving the problem keeps the depth near log₂ n, which is why fast exponentiation handles huge exponents. The Tower of Hanoi makes two recursive calls for one disc fewer, so 3 discs take 2³ − 1 = 7 moves while at most 4 calls are on the stack at once (down to hanoi(0)); 20 discs would take 1,048,575 moves with never more than 21 calls waiting.

Every input must reach a base case

A recursive function that misses its base case never stops calling itself. Here are two ways to get it wrong:

// no_base_case.cpp: two recursive functions that never stop.
#include <print>

// No base case at all: every call makes another call.
int count_down(int n) {
    return count_down(n - 1) + 1;
}

// A base case that some inputs never reach: odd or negative n step past n == 0.
int half_steps(int n) {
    if (n == 0) return 0;
    return half_steps(n - 2) + 1;
}

int main(int argc, char*[]) {
    std::println("half_steps(10) = {}", half_steps(10));
    if (argc > 1) std::println("half_steps(7) = {}", half_steps(7));
    if (argc > 2) std::println("count_down(5) = {}", count_down(5));
}

from session import run

run(r"""
clang++ -std=c++23 -Wall -Wextra no_base_case.cpp -o no_base_case
g++-16 -std=c++23 -Wall -Wextra no_base_case.cpp -o no_base_case_gcc
./no_base_case
./no_base_case odd
""")

$ clang++ -std=c++23 -Wall -Wextra no_base_case.cpp -o no_base_case
no_base_case.cpp:5:23: warning: all paths through this function will call itself [-Winfinite-recursion]
    5 | int count_down(int n) {
      |                       ^
1 warning generated.
$ g++-16 -std=c++23 -Wall -Wextra no_base_case.cpp -o no_base_case_gcc
no_base_case.cpp: In function 'int count_down(int)':
no_base_case.cpp:5:5: warning: infinite recursion detected [-Winfinite-recursion]
    5 | int count_down(int n) {
      |     ^~~~~~~~~~
no_base_case.cpp:6:22: note: recursive call
    6 |     return count_down(n - 1) + 1;
      |            ~~~~~~~~~~^~~~~~~
$ ./no_base_case
half_steps(10) = 5
$ ./no_base_case odd
[stopped by signal 11 (SIGSEGV): a shell reports exit status 139]

count_down has no base case at all, and both compilers notice: Apple clang warns that “all paths through this function will call itself”, GCC that it detected infinite recursion, both under -Winfinite-recursion. half_steps is the harder case. It has a base case, n == 0, but stepping down by 2 from an odd number jumps over 0, and from there n only gets smaller. Neither compiler warned about it. half_steps(10) works, and half_steps(7) called itself until the stack ran out and the program was stopped with SIGSEGV, the signal POSIX sends to a program that grows its stack past the limit. The line half_steps(10) = 5 is missing from that second run because it was still in the output buffer when the program was stopped.

Before you write a recursive function, name the quantity that shrinks on every call and the point where it stops. For half_steps that is n, which falls by 2, and the stopping point has to be “at or below zero”, not “exactly zero”.

Each pending call holds a frame, and the stack is small

Every call pushes a frame onto the stack, and every return pops it, so the stack holds exactly the calls that have not finished yet. A frame costs memory, and the stack is small and fixed. This program measures both:

// depth.cpp: the stack bytes one call takes, and how many calls the stack has room for.
#include <sys/resource.h>  // getrlimit, the POSIX call that reports the stack limit

#include <cstdint>
#include <print>
#include <string>

std::uintptr_t address_at_depth_0 = 0;
std::uintptr_t address_at_depth_1 = 0;

// Each call keeps a 1,024-byte buffer in its frame, so frames are big and easy to measure.
int dive(int depth, int target) {
    volatile char buffer[1024];  // volatile: the compiler must keep the buffer
    buffer[0] = 1;
    auto here = reinterpret_cast<std::uintptr_t>(&buffer[0]);
    if (depth == 0) address_at_depth_0 = here;
    if (depth == 1) address_at_depth_1 = here;
    if (depth == target) return depth;
    return dive(depth + 1, target) + buffer[0] - 1;
}

int main(int argc, char* argv[]) {
    int target = argc > 1 ? std::stoi(argv[1]) : 1000;
    dive(0, target);
    // the stack grows towards lower addresses
    std::uintptr_t frame = address_at_depth_0 - address_at_depth_1;
    rlimit limit{};
    getrlimit(RLIMIT_STACK, &limit);
    std::println("reached depth {}", target);
    std::println("one call of dive uses {} bytes of stack", frame);
    std::println("the stack limit is {} bytes: room for about {} calls", limit.rlim_cur, limit.rlim_cur / frame);
}

from session import run

# -O0 keeps every call as it is written. The search runs depth again and again, halving the range each time.
run(r"""
clang++ -std=c++23 -O0 depth.cpp -o depth_clang && ./depth_clang 1000
g++-16 -std=c++23 -O0 depth.cpp -o depth_gcc && ./depth_gcc 1000
./depth_clang 100000
lo=1000; hi=100000; while [ $((hi - lo)) -gt 1 ]; do mid=$(((lo + hi) / 2)); if ./depth_clang $mid > /dev/null; then lo=$mid; else hi=$mid; fi; done 2> /dev/null; echo "deepest call that worked, Apple clang build: $lo"
lo=1000; hi=100000; while [ $((hi - lo)) -gt 1 ]; do mid=$(((lo + hi) / 2)); if ./depth_gcc $mid > /dev/null; then lo=$mid; else hi=$mid; fi; done 2> /dev/null; echo "deepest call that worked, GCC build: $lo"
""")

$ clang++ -std=c++23 -O0 depth.cpp -o depth_clang && ./depth_clang 1000
reached depth 1000
one call of dive uses 1104 bytes of stack
the stack limit is 8372224 bytes: room for about 7583 calls
$ g++-16 -std=c++23 -O0 depth.cpp -o depth_gcc && ./depth_gcc 1000
reached depth 1000
one call of dive uses 1072 bytes of stack
the stack limit is 8372224 bytes: room for about 7809 calls
$ ./depth_clang 100000
[stopped by signal 11 (SIGSEGV): a shell reports exit status 139]
$ lo=1000; hi=100000; while [ $((hi - lo)) -gt 1 ]; do mid=$(((lo + hi) / 2)); if ./depth_clang $mid > /dev/null; then lo=$mid; else hi=$mid; fi; done 2> /dev/null; echo "deepest call that worked, Apple clang build: $lo"
deepest call that worked, Apple clang build: 7579
$ lo=1000; hi=100000; while [ $((hi - lo)) -gt 1 ]; do mid=$(((lo + hi) / 2)); if ./depth_gcc $mid > /dev/null; then lo=$mid; else hi=$mid; fi; done 2> /dev/null; echo "deepest call that worked, GCC build: $lo"
deepest call that worked, GCC build: 7805

At -O0, one call of dive used a little more than its 1,024-byte buffer: 1,104 bytes with Apple clang and 1,072 with GCC, because a frame also holds the parameters, saved registers and the return address. getrlimit, a POSIX call, reported the limit of the main thread’s stack: 8,372,224 bytes (8,176 KiB, the value ulimit -s prints). Dividing the two gives an estimate of how deep dive can go, and the search found the deepest call that worked a few calls short of each estimate:

The rest of the stack was taken by main, the code that runs before it and the program’s environment. One level deeper and the program crashed, as ./depth_clang 100000 did: a stack overflowstack overflow: What happens when the calls still running need more stack than the thread has: the program is stopped, on POSIX systems with SIGSEGV. AddressSanitizer reports it as a stack-overflow with the function that caused it..

That limit differs between systems and between threads. A Windows executable gets a 1 MB stack unless it is linked with another /STACK size, so the same program would manage only about an eighth of the depth there. On macOS, threads other than the main thread get 512 KB by default, according to Apple’s threading guide. Programming judges set limits of their own. So a recursion depth that grows with the size of the input, such as a list of a million items or a path through a big grid, is a crash waiting for the first large input.

AddressSanitizer names the problem

A bare SIGSEGV says nothing about the cause. Built with -fsanitize=address, the same program reports a stack overflow and the function that caused it:

from session import run

# AddressSanitizer reports the overflow instead of a bare crash. Its report is long, so the session keeps the
# error line, the first two frames and the summary, and hides the process number and addresses, which change on
# every run.
run(r"""
clang++ -std=c++23 -O0 -g -fsanitize=address depth.cpp -o depth_asan && ./depth_asan 100000
g++-16 -std=c++23 -O0 -g -fsanitize=address depth.cpp -o depth_asan_gcc && ./depth_asan_gcc 100000
""", keep=r"ERROR: AddressSanitizer|^\s+#[01] |SUMMARY", replace=[(r"==\d+==", "==…=="), (r"0x[0-9a-f]+", "0x…")])

$ clang++ -std=c++23 -O0 -g -fsanitize=address depth.cpp -o depth_asan && ./depth_asan 100000
==…==ERROR: AddressSanitizer: stack-overflow on address 0x… (pc 0x… bp 0x… sp 0x… T0)
    #0 0x… in dive(int, int) depth.cpp:12
    #1 0x… in dive(int, int) depth.cpp:19
SUMMARY: AddressSanitizer: stack-overflow depth.cpp:12 in dive(int, int)
[exit status 134]
$ g++-16 -std=c++23 -O0 -g -fsanitize=address depth.cpp -o depth_asan_gcc && ./depth_asan_gcc 100000
==…==ERROR: AddressSanitizer: stack-overflow on address 0x… (pc 0x… bp 0x… sp 0x… T0)
    #0 0x… in dive(int, int) depth.cpp:12
    #1 0x… in dive(int, int) depth.cpp:19
SUMMARY: AddressSanitizer: stack-overflow depth.cpp:12 in dive(int, int)
[exit status 134]

The report names the error (stack-overflow), the function (dive) and the lines: line 12, where each call sets up its frame, and line 19, the recursive call, which repeats in every frame below it. AddressSanitizer makes frames larger and the program about twice as slow, so use it to find bugs, not to measure depths.

A tail call saves a frame only when the optimiser chooses

A tail calltail call: A call that is the last thing a function does, as in return sum_to(n - 1, total + n);. A compiler may reuse the caller's frame for it, turning the recursion into a loop, but C++ does not require that. is a call that is the last thing a function does: return sum_to(n - 1, total + n); has nothing left to do after the call returns. A compiler is then free to let the called function take over the caller’s frame, so the recursion runs like a loop, in a fixed amount of stack. The C++ standard does not require this, so it happens only where a compiler, at a given optimisation level, decides to do it:

// tail.cpp: adds 1 + 2 + ... + n with a tail call, a call that is the last thing done.
#include <cstdint>
#include <print>
#include <string>

std::int64_t sum_to(std::int64_t n, std::int64_t total) {
    if (n == 0) return total;
    return sum_to(n - 1, total + n);  // nothing is left to do after this call returns
}

int main(int argc, char* argv[]) {
    std::int64_t n = argc > 1 ? std::stoll(argv[1]) : 10;
    std::println("sum_to({}) = {}", n, sum_to(n, 0));
}

// musttail.cpp: the same function; the attribute demands a real tail call (Clang).
#include <cstdint>
#include <print>
#include <string>

std::int64_t sum_to(std::int64_t n, std::int64_t total) {
    if (n == 0) return total;
    [[clang::musttail]] return sum_to(n - 1, total + n);
}

int main(int argc, char* argv[]) {
    std::int64_t n = argc > 1 ? std::stoll(argv[1]) : 10;
    std::println("sum_to({}) = {}", n, sum_to(n, 0));
}

// musttail_gnu.cpp: the same demand in GCC's own spelling of the attribute.
#include <cstdint>

std::int64_t sum_to(std::int64_t n, std::int64_t total) {
    if (n == 0) return total;
    [[gnu::musttail]] return sum_to(n - 1, total + n);
}

from session import run

# Ten million nested calls need far more than the 8 MB stack, unless the compiler turns them into a loop.
run(r"""
clang++ -std=c++23 -O0 tail.cpp -o tail_clang_O0
clang++ -std=c++23 -O1 tail.cpp -o tail_clang_O1
g++-16 -std=c++23 -O1 tail.cpp -o tail_gcc_O1
g++-16 -std=c++23 -O2 tail.cpp -o tail_gcc_O2
./tail_clang_O0 10000000
./tail_clang_O1 10000000
./tail_gcc_O1 10000000
./tail_gcc_O2 10000000
clang++ -std=c++23 -O0 musttail.cpp -o musttail_clang && ./musttail_clang 10000000
g++-16 -std=c++23 -O0 musttail.cpp -o musttail_gcc && ./musttail_gcc 10000000
g++-16 -std=c++23 -O0 -c musttail_gnu.cpp
clang++ -std=c++23 -O0 -c musttail_gnu.cpp
""")

$ clang++ -std=c++23 -O0 tail.cpp -o tail_clang_O0
$ clang++ -std=c++23 -O1 tail.cpp -o tail_clang_O1
$ g++-16 -std=c++23 -O1 tail.cpp -o tail_gcc_O1
$ g++-16 -std=c++23 -O2 tail.cpp -o tail_gcc_O2
$ ./tail_clang_O0 10000000
[stopped by signal 11 (SIGSEGV): a shell reports exit status 139]
$ ./tail_clang_O1 10000000
sum_to(10000000) = 50000005000000
$ ./tail_gcc_O1 10000000
[stopped by signal 11 (SIGSEGV): a shell reports exit status 139]
$ ./tail_gcc_O2 10000000
sum_to(10000000) = 50000005000000
$ clang++ -std=c++23 -O0 musttail.cpp -o musttail_clang && ./musttail_clang 10000000
sum_to(10000000) = 50000005000000
$ g++-16 -std=c++23 -O0 musttail.cpp -o musttail_gcc && ./musttail_gcc 10000000
sum_to(10000000) = 50000005000000
$ g++-16 -std=c++23 -O0 -c musttail_gnu.cpp
$ clang++ -std=c++23 -O0 -c musttail_gnu.cpp
musttail_gnu.cpp:6:7: warning: unknown attribute 'gnu::musttail' ignored [-Wunknown-attributes]
    6 |     [[gnu::musttail]] return sum_to(n - 1, total + n);
      |       ^~~~~~~~~~~~~
1 warning generated.

So a tail-recursive function can work in a release build and crash in a debug build of the same code. The attribute [[clang::musttail]] on the return demands a real tail call even at -O0, and the compiler must report an error when it cannot make one; in this session both Apple clang and GCC 16 accepted it and printed the sum. GCC documents its own spelling, [[gnu::musttail]]: the last two commands show GCC accepting it and Apple clang ignoring it with a warning, unknown attribute. Both spellings are compiler extensions, not standard C++, so portable code that may recurse deeply should be written as a loop.

Memoisation turns repeated calls into one call each

Depth is not the only cost. The textbook Fibonacci function makes two recursive calls, and they recompute the same values over and over:

// fib.cpp: Fibonacci numbers, plain and memoised, counting the calls each one makes.
#include <cstdint>
#include <print>
#include <vector>

std::int64_t calls = 0;

std::int64_t fib(int n) {
    ++calls;
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);  // two calls, and they repeat each other's work
}

// memo[k] holds fib(k) once known, and 0 before that (n < 2 returns before it looks).
std::int64_t fib_memo(int n, std::vector<std::int64_t>& memo) {
    ++calls;
    if (n < 2) return n;
    if (memo[n] == 0) memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo);
    return memo[n];
}

int main() {
    for (int n : {10, 20, 30, 40}) {
        calls = 0;
        std::int64_t plain = fib(n);
        std::int64_t plain_calls = calls;

        calls = 0;
        std::vector<std::int64_t> memo(n + 1, 0);
        std::int64_t remembered = fib_memo(n, memo);

        std::println("fib({}) = {} ({}): {} calls plain, {} calls memoised", n, plain, remembered, plain_calls, calls);
    }
}

fib(10) = 55 (55): 177 calls plain, 19 calls memoised
fib(20) = 6765 (6765): 21891 calls plain, 39 calls memoised
fib(30) = 832040 (832040): 2692537 calls plain, 59 calls memoised
fib(40) = 102334155 (102334155): 331160281 calls plain, 79 calls memoised

fib(40) made 331,160,281 calls, and every increase of n by 10 multiplied the count by more than 120: the plain function is exponential, and its call count grows like the Fibonacci numbers themselves. Memoisationmemoisation: Keeping the result of a call the first time it is computed and returning the stored result when the same arguments come again, so that repeated work is done only once. keeps each answer the first time it is computed, here in a std::vector passed by reference, and returns the stored answer afterwards. The memoised fib(40) made 79 calls, 2n − 1, and its depth is still about n; the GCC build counted the same calls.

Recursion depth and the number of calls are different costs, and this lesson’s measurements tell them apart: Fibonacci needed memoisation for the calls, and the deep sum needed a loop for the depth.

Practise: flood fill, recursively and with your own stack

A flood fill colours a whole region, as a paint program’s bucket tool does: start at one cell, colour it, then fill each open neighbour. The recursive version is short, and its depth grows with the size of the region. Write it, and then an iterative version that keeps the cells still to visit in a std::vector of its own, on the heap, where a few million entries fit easily.

// fill.h: the two functions of the exercise. Keep these declarations as they are.
#pragma once
#include <string>
#include <vector>

// A grid is a list of rows of the same length: '.' is an open cell and '#' a wall.
using Grid = std::vector<std::string>;

// Both functions fill the open region that contains the cell (row, col): every '.' that
// can be reached from it by steps up, down, left or right through '.' cells becomes
// 'o'. They change nothing when (row, col) is outside the grid or is not '.'.
// fill_recursive calls itself for each of the four neighbours; fill_iterative keeps the
// cells still to visit in a std::vector instead.
void fill_recursive(Grid& grid, int row, int col);
void fill_iterative(Grid& grid, int row, int col);

// fill.cpp: the starter. Both functions compile but fill nothing yet.
#include "fill.h"

void fill_recursive(Grid& grid, int row, int col) {
    (void)grid;  // remove these three lines when you use the parameters
    (void)row;
    (void)col;
}

void fill_iterative(Grid& grid, int row, int col) {
    (void)grid;
    (void)row;
    (void)col;
}

// fill_test.cpp: the public tests. Build them with your fill.cpp. With --large, both
// functions also fill one open region of 2,000 by 2,000 cells.
#include <cstdio>
#include <cstdlib>
#include <print>
#include <string_view>

#include "fill.h"

int checks = 0;
int failures = 0;

void check(bool passed, std::string_view what) {
    ++checks;
    if (!passed) {
        ++failures;
        std::println("FAIL: {}", what);
    }
}

using FillFunction = void (*)(Grid&, int, int);  // either of the two functions

void small_tests(FillFunction fill, std::string_view name) {
    Grid rooms{"..#..", ".##..", "....#", "#####", "..#.."};
    fill(rooms, 0, 0);
    check(rooms == Grid{"oo#oo", "o##oo", "oooo#", "#####", "..#.."}, std::string(name) + ": the region around the top left");
    fill(rooms, 4, 0);
    check(rooms[4] == "oo#..", std::string(name) + ": a second region, below the wall");
    Grid corners{".#", "#."};
    fill(corners, 0, 0);
    check(corners == Grid{"o#", "#."}, std::string(name) + ": no diagonal steps");
    Grid walls{"##", "#."};
    fill(walls, 0, 0);
    fill(walls, -1, 5);
    check(walls == Grid{"##", "#."}, std::string(name) + ": a wall or a cell outside the grid changes nothing");
}

long long filled_cells(const Grid& grid) {
    long long count = 0;
    for (const auto& row : grid) {
        for (char c : row) count += c == 'o';
    }
    return count;
}

void large_test(FillFunction fill, std::string_view name) {
    Grid big(2000, std::string(2000, '.'));
    fill(big, 1000, 1000);
    std::println("large grid, {}: {} cells filled", name, filled_cells(big));
    // print it now: if the next test crashes, the line is already out
    std::fflush(stdout);
}

int main(int argc, char* argv[]) {
    small_tests(fill_iterative, "fill_iterative");
    small_tests(fill_recursive, "fill_recursive");
    if (failures == 0) {
        std::println("All {} checks passed", checks);
    } else {
        std::println("{} of {} checks failed", failures, checks);
    }
    std::fflush(stdout);
    if (argc > 1 && std::string_view{argv[1]} == "--large") {
        large_test(fill_iterative, "fill_iterative");
        large_test(fill_recursive, "fill_recursive");
    }
    return failures == 0 ? EXIT_SUCCESS : EXIT_FAILURE;
}

from session import run

# The public tests built with the starter file, which fills nothing yet.
run(r"""
cd exercise && clang++ -std=c++23 -Wall -Wextra fill.cpp fill_test.cpp -o fill_test && ./fill_test
""")

$ cd exercise && clang++ -std=c++23 -Wall -Wextra fill.cpp fill_test.cpp -o fill_test && ./fill_test
FAIL: fill_iterative: the region around the top left
FAIL: fill_iterative: a second region, below the wall
FAIL: fill_iterative: no diagonal steps
FAIL: fill_recursive: the region around the top left
FAIL: fill_recursive: a second region, below the wall
FAIL: fill_recursive: no diagonal steps
6 of 8 checks failed
[exit status 1]

1. Write fill_recursive: return at once when the cell is outside the grid or is not '.'; otherwise set it to 'o' and call fill_recursive for the four neighbours.
2. Write fill_iterative: put the first cell in a std::vector of pending cells. Until that vector is empty, remove its last cell (read it with back(), then call pop_back()); ignore a cell that lies outside the grid or holds anything but '.', and colour any other one and push its four neighbours onto the vector.
3. Build with clang++ -std=c++23 -Wall -Wextra fill.cpp fill_test.cpp -o fill_test and run ./fill_test until it prints All 8 checks passed.
4. Run ./fill_test --large. It fills one open grid of 2,000 by 2,000 cells with each function. Expect fill_iterative to report 4,000,000 cells filled, and fill_recursive to crash with a stack overflow, with either compiler at -O0 or -O2: four million cells are far more frames than 8 MB can hold.

A first hint for step 2: a small struct such as struct Cell { int row; int col; }; makes the vector easy to read, std::vector<Cell> pending{{row, col}};.

Once both fills pass, take the questions on base cases, frames, depth, tail calls and memoisation. The first ones probe the idea you have answered worst so far, and the note on each option says which part of the lesson it rests on:

Interview questions

Fresher · What is a stack frame, and what does a recursive call cost?

A stack frame is the block of the call stack that belongs to one call that has not returned yet: its parameters, its local variables, saved registers and the address to return to. Each call pushes a frame and each return pops it, so a recursion n levels deep holds n frames at once. That costs memory proportional to the depth, from a limited stack (8,372,224 bytes for the main thread on the Mac of this lesson, 1 MB by default for Windows executables), plus a little time per call. Too deep, and the program crashes with a stack overflow; C++ does not guarantee that tail calls reuse a frame.

Follow-up questions here tend to probe threads and the cost of a fix. Pick your answers before you read the note on each option:

Key takeaways

• A recursive function needs a base case that every input reaches; name what shrinks on each call and where it stops.
• Every pending call holds a stack frame with its own parameters and locals; the frames come off in reverse order as the calls return.
• Frame size times depth must fit the stack: dive with 1 KB of locals reached 7,579 calls with Apple clang and 7,805 with GCC, a few calls short of the estimate from getrlimit.
• Tail calls become loops only when the optimiser chooses: Apple clang from -O1, GCC from -O2 here. [[clang::musttail]] demands it, but it is not standard C++.
• Memoisation fixes repeated work (fib(40): 331,160,281 calls down to 79); an explicit stack on the heap fixes depth.