Explicit stack

Why it matters

A recursive function keeps its unfinished work on the call stack. The call stack is a block of memory that the operating system gives each running program, and it has a fixed size. On the Linux machine used to check this lesson, ulimit -s reports 8192, which means 8192 KB, or 8 MB. Yours may differ. A recursive search over a large input can need more room than that. When it does, the program stops with a segmentation fault and usually prints no message about the cause.

The fix is to keep the unfinished work in a data structure that you control. That structure lives in the heap, the memory a program asks for while it runs, which is much larger than the call stack. This is called an explicit stack, because the stack is written out in your code rather than hidden inside the function calls.

The Flood fill lesson in this module solved the problem with recursion. This lesson uses the same problem and turns the recursion into a loop, one step at a time.

What the call stack does

Each function call needs a small block of memory to hold its input values and its local variables. This block is called a frame. When one function calls another, the new frame goes on top of the old one. When a function returns, its frame is removed, and the program continues in the frame below it.

A stack is a pile where the last item added is the first one taken off. This rule is often called LIFO, which stands for last in, first out. Think of a stack of plates in a cafeteria. You put a clean plate on the top, and you take a plate from the top. You never take a plate from the middle.

A recursive call that has not returned yet keeps its frame on the call stack. A recursive flood fill that goes 1000 cells deep has 1000 frames waiting at once. The number of frames waiting at the same time is called the depth.

Building the stack yourself

An explicit stack is a stack that your code creates. In C++ the easiest choice is std::vector, the standard library's resizable array. Four of its functions cover everything a stack needs:

push_back(x) adds x to the top.
back() reads the item on the top without removing it.
pop_back() removes the item on the top. It does not return the value, so read it with back() first.
empty() returns true when the vector has no items.

Every recursive function can be written with this pattern:

Put the first piece of work on the stack.
While the stack is not empty, read the top item with back() and remove it with pop_back().
Do the work for that item. Each piece of work that a recursive call would have made becomes an item that you push_back onto the stack.
Go back to step 2.

The loop does the same job as the recursion. The calls that would have waited on the call stack are now items waiting in the vector. The vector can grow as large as the memory on the machine allows.

Adding or removing an item at the top takes about the same time whatever the size of the vector. Now and then the vector runs out of room and copies its items into a bigger block, but that happens rarely enough that the average cost per push stays small. This is why a loop over an explicit stack runs in time that grows with the number of items it handles.

The problem: flood fill

A grid is a list of rows, and each row is a line of characters. In this lesson a . means an open cell and a # means a wall. Flood fill starts at one open cell and changes every open cell connected to it to o. Two cells are connected when one is directly above, below, left or right of the other. Diagonal neighbours do not count.

Take this grid:

..#..
.##..
#...#
..#..

Start at row 0, column 0. The cell is open, so it becomes o. Its neighbours are checked next. The cell below it is open, so it also becomes o. The cell to its right is open. The cell diagonal to it, at row 1, column 1, is a wall, so it is never reached through that route. The fill ends with three cells changed. Those cells are (0,0), (0,1) and (1,0), with row and column counted from 0. Each cell is written as (row,column).

The recursive version

Here is the recursive flood fill from the earlier lesson. Each call handles one cell. It returns at once if the cell is outside the grid or is not open. Otherwise it marks the cell and calls itself for the four neighbours.

#include <iostream>
#include <string>
#include <vector>
 
using Grid = std::vector<std::string>;
 
bool inside(const Grid& grid, int row, int col) {
    return row >= 0 && row < static_cast<int>(grid.size()) &&
           col >= 0 && col < static_cast<int>(grid[row].size());
}
 
// Recursive version: each call handles one cell and calls itself for the four neighbours.
void fill_recursive(Grid& grid, int row, int col) {
    if (!inside(grid, row, col) || grid[row][col] != '.') {
        return;
    }
    grid[row][col] = 'o';
    fill_recursive(grid, row + 1, col);
    fill_recursive(grid, row - 1, col);
    fill_recursive(grid, row, col + 1);
    fill_recursive(grid, row, col - 1);
}

The four recursive calls are the pending work. While the first call runs, the other three are waiting on the call stack, in the frames of the calls that made them.

Worked example 1: the same fill with a loop

The explicit version keeps a vector of cells to handle. Each item is a row and column pair, stored in a small struct. The struct makes the code easier to read than a pair of numbers.

C++ · editable

#include <iostream>
#include <string>
#include <vector>

using Grid = std::vector<std::string>;

struct Cell {
    int row;
    int col;
};

bool inside(const Grid& grid, int row, int col) {
    return row >= 0 && row < static_cast<int>(grid.size()) &&
           col >= 0 && col < static_cast<int>(grid[row].size());
}

// Recursive version: each call handles one cell and calls itself for the four neighbours.
void fill_recursive(Grid& grid, int row, int col) {
    if (!inside(grid, row, col) || grid[row][col] != '.') {
        return;
    }
    grid[row][col] = 'o';
    fill_recursive(grid, row + 1, col);
    fill_recursive(grid, row - 1, col);
    fill_recursive(grid, row, col + 1);
    fill_recursive(grid, row, col - 1);
}

// Explicit stack version: a vector holds the cells still waiting to be handled.
void fill_stack(Grid& grid, int row, int col) {
    std::vector<Cell> pending;
    pending.push_back({row, col});
    while (!pending.empty()) {
        Cell cell = pending.back();
        pending.pop_back();
        if (!inside(grid, cell.row, cell.col) || grid[cell.row][cell.col] != '.') {
            continue;
        }
        grid[cell.row][cell.col] = 'o';
        pending.push_back({cell.row + 1, cell.col});
        pending.push_back({cell.row - 1, cell.col});
        pending.push_back({cell.row, cell.col + 1});
        pending.push_back({cell.row, cell.col - 1});
    }
}

void print_grid(const Grid& grid) {
    for (const std::string& line : grid) {
        std::cout << line << "\n";
    }
}

int main() {
    Grid start = {
        "..#..",
        ".##..",
        "#...#",
        "..#..",
    };

Grid a = start;
    fill_recursive(a, 0, 0);
    std::cout << "recursive:\n";
    print_grid(a);

Grid b = start;
    fill_stack(b, 0, 0);
    std::cout << "explicit stack:\n";
    print_grid(b);

std::cout << "same result: " << (a == b ? "yes" : "no") << "\n";
}

The program includes fill_recursive so that both versions can run on the same grid. The explicit version is fill_stack. It starts with one cell in pending. Each loop pass takes one cell off the back, checks it, marks it and adds its four neighbours. When the vector is empty, every reachable cell has been handled.

Output:

recursive:
oo#..
o##..
#...#
..#..
explicit stack:
oo#..
o##..
#...#
..#..
same result: yes

The two versions give the same grid. The rest of this lesson looks at what happens inside the loop.

Worked example 2: tracing the stack

A trace shows what the stack holds at each step. This program fills a 2 by 2 grid with one wall in the bottom right corner. It prints a line for each cell taken off the stack. A line says "fill" if the cell is open and "skip" if the cell is outside the grid, is a wall, or was already filled. The number after stack size is the count of items still waiting after the cell was taken off, just before its neighbours are added.

C++ · editable

#include <iostream>
#include <string>
#include <vector>

using Grid = std::vector<std::string>;
struct Cell { int row; int col; };

bool inside(const Grid& grid, int row, int col) {
    return row >= 0 && row < static_cast<int>(grid.size()) &&
           col >= 0 && col < static_cast<int>(grid[row].size());
}

int main() {
    Grid grid = {
        "..",
        ".#",
    };
    std::vector<Cell> pending;
    pending.push_back({0, 0});
    int step = 0;
    while (!pending.empty()) {
        Cell cell = pending.back();
        pending.pop_back();
        step++;
        if (!inside(grid, cell.row, cell.col) || grid[cell.row][cell.col] != '.') {
            std::cout << "step " << step << ": skip (" << cell.row << "," << cell.col << ")\n";
            continue;
        }
        grid[cell.row][cell.col] = 'o';
        std::cout << "step " << step << ": fill (" << cell.row << "," << cell.col << ")"
                  << "  stack size before pushes: " << pending.size() << "\n";
        pending.push_back({cell.row + 1, cell.col});
        pending.push_back({cell.row - 1, cell.col});
        pending.push_back({cell.row, cell.col + 1});
        pending.push_back({cell.row, cell.col - 1});
    }
    for (const std::string& line : grid) {
        std::cout << line << "\n";
    }
}

Output:

step 1: fill (0,0)  stack size before pushes: 0
step 2: skip (0,-1)
step 3: fill (0,1)  stack size before pushes: 2
step 4: skip (0,0)
step 5: skip (0,2)
step 6: skip (-1,1)
step 7: skip (1,1)
step 8: skip (-1,0)
step 9: fill (1,0)  stack size before pushes: 0
step 10: skip (1,-1)
step 11: skip (1,1)
step 12: skip (0,0)
step 13: skip (2,0)
oo
o#

Step 1 takes (0,0) off the stack. The stack is empty after that pop, so the count is 0. The cell is filled, and its four neighbours are pushed in the order down, up, right, left: (1,0), (-1,0), (0,1), (0,-1). The last pushed item, (0,-1), is on the top.

Step 2 takes (0,-1) off. It is outside the grid, so it is skipped. Step 3 takes (0,1) off. It is open, so it is filled. At that moment the stack holds (1,0) and (-1,0), so the count is 2. Its neighbours go on the stack, and steps 4 to 8 remove and skip the ones that are not useful. Step 9 fills the last open cell, (1,0). Steps 10 to 13 skip the four neighbours it pushed.

Notice that the stack holds items that will be skipped. Some pushes lead nowhere, because the cell is outside the grid or already filled. That is normal. The check at the top of the loop is what makes them harmless.

Worked example 3: a grid too big for recursion

The stack approach matters when the grid is large. This program fills an open 2000 by 2000 grid. The explicit version counts the cells it fills and the largest number of items the stack holds at one time. The recursive version runs the same fill, but it prints nothing at the end.

C++ · editable

#include <iostream>
#include <string>
#include <utility>
#include <vector>

using Grid = std::vector<std::string>;

struct Cell {
    int row;
    int col;
};

bool inside(const Grid& grid, int row, int col) {
    return row >= 0 && row < static_cast<int>(grid.size()) &&
           col >= 0 && col < static_cast<int>(grid[row].size());
}

void fill_recursive(Grid& grid, int row, int col) {
    if (!inside(grid, row, col) || grid[row][col] != '.') {
        return;
    }
    grid[row][col] = 'o';
    fill_recursive(grid, row + 1, col);
    fill_recursive(grid, row - 1, col);
    fill_recursive(grid, row, col + 1);
    fill_recursive(grid, row, col - 1);
}

// Returns how many cells were filled and the largest stack size reached.
std::pair<long long, std::size_t> fill_stack(Grid& grid, int row, int col) {
    std::vector<Cell> pending;
    std::size_t largest = 0;
    long long filled = 0;
    pending.push_back({row, col});
    while (!pending.empty()) {
        if (pending.size() > largest) {
            largest = pending.size();
        }
        Cell cell = pending.back();
        pending.pop_back();
        if (!inside(grid, cell.row, cell.col) || grid[cell.row][cell.col] != '.') {
            continue;
        }
        grid[cell.row][cell.col] = 'o';
        filled++;
        pending.push_back({cell.row + 1, cell.col});
        pending.push_back({cell.row - 1, cell.col});
        pending.push_back({cell.row, cell.col + 1});
        pending.push_back({cell.row, cell.col - 1});
    }
    return {filled, largest};
}

int main(int argc, char** argv) {
    int size = 2000;
    bool use_recursion = argc > 1;
    Grid grid(size, std::string(size, '.'));
    if (use_recursion) {
        fill_recursive(grid, 0, 0);
        std::cout << "recursion finished\n";
        return 0;
    }
    auto [filled, largest] = fill_stack(grid, 0, 0);
    std::cout << "filled " << filled << " cells, largest stack " << largest << "\n";
}

Compile it with g++ -std=c++20 -Wall -o big big.cpp. Run ./big for the explicit version, or ./big rec for the recursive version. The function returns a std::pair, which holds two values, and auto [filled, largest] unpacks them into two variables.

Output of the explicit version:

filled 4000000 cells, largest stack 9995004

The recursive version prints nothing. The shell reports exit code 139, which means the program was stopped by a segmentation fault. The fill goes 4 million cells deep in the worst case, and each call needs at least a return address on the call stack. That is far more than 8 MB, so the call stack runs out first.

The explicit version fills all 4 million cells. Its largest stack size is 9995004, which is more than the number of cells. The reason is that each filled cell pushes four neighbours, and the same open cell can be pushed more than once before it is filled. The stack holds those extra copies until they are popped and skipped. Each entry holds two int values, which take 8 bytes, so the stack needs about 80 million bytes at its largest. That is a lot of memory, but it is heap memory, which is limited by the machine's free memory and not by the 8 MB call stack limit.

Improving the stack: mark a cell when it is pushed

The stack above marks a cell only when it is taken off. A cell can therefore be pushed many times. Marking the cell at the moment it is pushed means it is pushed exactly once. The loop below uses arrays of row and column offsets, so the four neighbours are handled in one loop.

C++ · editable

#include <iostream>
#include <string>
#include <utility>
#include <vector>

using Grid = std::vector<std::string>;
struct Cell { int row; int col; };

bool inside(const Grid& grid, int row, int col) {
    return row >= 0 && row < static_cast<int>(grid.size()) &&
           col >= 0 && col < static_cast<int>(grid[row].size());
}

// Mark each cell as soon as it is pushed, so it is never pushed twice.
std::pair<long long, std::size_t> fill_mark_on_push(Grid& grid, int row, int col) {
    std::vector<Cell> pending;
    std::size_t largest = 0;
    long long filled = 1;
    grid[row][col] = 'o';
    pending.push_back({row, col});
    while (!pending.empty()) {
        if (pending.size() > largest) {
            largest = pending.size();
        }
        Cell cell = pending.back();
        pending.pop_back();
        const int dr[] = {1, -1, 0, 0};
        const int dc[] = {0, 0, 1, -1};
        for (int k = 0; k < 4; k++) {
            int r = cell.row + dr[k];
            int c = cell.col + dc[k];
            if (inside(grid, r, c) && grid[r][c] == '.') {
                grid[r][c] = 'o';
                filled++;
                pending.push_back({r, c});
            }
        }
    }
    return {filled, largest};
}

int main() {
    Grid grid(2000, std::string(2000, '.'));
    auto [filled, largest] = fill_mark_on_push(grid, 0, 0);
    std::cout << "filled " << filled << " cells, largest stack " << largest << "\n";
}

Output:

filled 4000000 cells, largest stack 1999001

Now each cell is pushed exactly once, so the stack never holds more entries than there are cells. The largest stack drops from 9995004 to 1999001, and the result is the same 4000000 cells. The change is in when the cell is marked: as it joins the stack, not as it leaves.

Common mistakes

Popping from an empty stack

The loop must check empty() before it reads or removes the top item. This program breaks that rule:

#include <iostream>
#include <vector>
 
int main() {
    std::vector<int> stack;
    stack.push_back(7);
    stack.pop_back();
    std::cout << stack.back() << "\n";
}

Compile it with the standard library checks turned on, using the -D_GLIBCXX_ASSERTIONS flag:

g++ -std=c++20 -Wall -D_GLIBCXX_ASSERTIONS -o m_empty m_empty.cpp

Running it prints an assertion message and stops with exit code 134. The file path and line number depend on where your C++ library is installed:

/usr/include/c++/15/bits/stl_vector.h:1370: constexpr std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::back() [with _Tp = int; _Alloc = std::allocator<int>; reference = int&]: Assertion '!this->empty()' failed.

Without that flag, reading back() on an empty vector is undefined behaviour. The program might print a random number or crash later. In the loop from this lesson, the while (!pending.empty()) line prevents this, so the body never runs on an empty stack.

Checking the bounds after indexing

The check inside(...) must come before grid[row][col]. This program indexes a row that does not exist:

#include <iostream>
#include <string>
#include <vector>
 
using Grid = std::vector<std::string>;
 
int main() {
    Grid grid = {"..", ".."};
    int row = -1;
    std::cout << grid.at(row).at(0) << "\n";
}

The at function checks the index and throws an error when it is out of range. Its output is:

terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 18446744073709551615) >= this->size() (which is 2)

The number 18446744073709551615 is -1 read as an unsigned number, because the index type is unsigned. Writing grid[row] instead of grid.at(row) skips the check, so the program may not print any message before it fails. Always test the row and column before reading the grid.

Forgetting to mark the cell

If the loop never writes o into the grid, the open-cell test is always true. Each cell is then pushed again every time it is reached. The stack never shrinks to empty, so the loop does not end, and the stack keeps growing until the program runs out of memory. Mark the cell before adding its neighbours.

Expecting the same visit order

The explicit stack gives the same set of filled cells, but not always the same order. The recursive version handles its first neighbour completely before it looks at the second. The stack takes the last pushed neighbour first. On a 2 by 2 open grid, the recursive version fills the cells in the order (0,0), (1,0), (1,1), (0,1). The explicit version, as traced in Exercise 1, fills them in the order (0,0), (0,1), (1,1), (1,0). Both give a full fill, but a program that depends on the order of visits must be checked against the order it actually produces.

Practice

Exercise 1: The visit order on a 2 by 2 grid

A 2 by 2 grid has no walls. Write down the order in which fill_stack visits the four cells, starting from (0,0). Then check your answer with the program.

Show the answer

The order is (0,0), (0,1), (1,1), (1,0). With the wall removed from the trace program, its fill lines are:

step 1: fill (0,0)  stack size before pushes: 0
step 3: fill (0,1)  stack size before pushes: 2
step 7: fill (1,1)  stack size before pushes: 2
step 8: fill (1,0)  stack size before pushes: 5

The last neighbour pushed from (0,0) is (0,-1), which is skipped. The next item is (0,1), which is filled first. Its neighbours are pushed on top, and the walk continues from there before the (1,0) item that was pushed first is reached.

Exercise 2: Return the number of cells filled

Change fill_stack so it returns the number of cells it filled, as an int. Run it twice on the same grid from (0,0). The second call should return 0.

Show the answer

Count each cell as it is marked, and return the count at the end. The second call finds no open cells at (0,0), because the first call already changed them to o.

C++ · editable

#include <iostream>
#include <string>
#include <vector>

using Grid = std::vector<std::string>;
struct Cell { int row; int col; };

bool inside(const Grid& grid, int row, int col) {
    return row >= 0 && row < static_cast<int>(grid.size()) &&
           col >= 0 && col < static_cast<int>(grid[row].size());
}

// Returns how many cells were filled.
int fill_count(Grid& grid, int row, int col) {
    const int dr[] = {1, -1, 0, 0};
    const int dc[] = {0, 0, 1, -1};
    int filled = 0;
    std::vector<Cell> pending{{row, col}};
    while (!pending.empty()) {
        Cell cell = pending.back();
        pending.pop_back();
        if (!inside(grid, cell.row, cell.col) || grid[cell.row][cell.col] != '.') {
            continue;
        }
        grid[cell.row][cell.col] = 'o';
        filled++;
        for (int k = 0; k < 4; k++) {
            pending.push_back({cell.row + dr[k], cell.col + dc[k]});
        }
    }
    return filled;
}

int main() {
    Grid grid = {
        "..#..",
        ".##..",
        "#...#",
        "..#..",
    };
    std::cout << "filled " << fill_count(grid, 0, 0) << "\n";
    std::cout << "filled again " << fill_count(grid, 0, 0) << "\n";
}

Output:

filled 3
filled again 0

Exercise 3: Why marking on push keeps the stack small

The mark-on-push version reached a largest stack of 1999001 on the 2000 by 2000 grid, and the first version reached 9995004. Explain why the difference happens. Then say how many times the stack can receive a given cell in the second version.

Show the answer

In the first version, a cell is marked only when it is taken off the stack. Before that, every filled neighbour of the cell may have pushed it again, so the same cell can sit in the stack several times. In the second version, a cell is marked as soon as it is pushed, so the test grid[r][c] == '.' fails for every later neighbour that finds it. Each cell is pushed exactly once. The stack therefore holds at most one entry per cell, and the largest size is about half the cell count in this grid.

Exercise 4: Sizes of every region

A region is a group of open cells that touch each other. Using the fill_count function from Exercise 2, count the size of every region in this grid, scanning each cell in order from the top left.

..#..
.##.#
#...#
..#..

Show the answer

Scan every cell. When an open cell is found, call fill_count from that cell. It fills the whole region and returns its size. The scan then goes on, and the filled cells are skipped because they are no longer ..

C++ · editable

#include <iostream>
#include <string>
#include <vector>

using Grid = std::vector<std::string>;
struct Cell { int row; int col; };

bool inside(const Grid& grid, int row, int col) {
    return row >= 0 && row < static_cast<int>(grid.size()) &&
           col >= 0 && col < static_cast<int>(grid[row].size());
}

int fill_count(Grid& grid, int row, int col) {
    const int dr[] = {1, -1, 0, 0};
    const int dc[] = {0, 0, 1, -1};
    int filled = 0;
    std::vector<Cell> pending{{row, col}};
    while (!pending.empty()) {
        Cell cell = pending.back();
        pending.pop_back();
        if (!inside(grid, cell.row, cell.col) || grid[cell.row][cell.col] != '.') {
            continue;
        }
        grid[cell.row][cell.col] = 'o';
        filled++;
        for (int k = 0; k < 4; k++) {
            pending.push_back({cell.row + dr[k], cell.col + dc[k]});
        }
    }
    return filled;
}

int main() {
    Grid grid = {
        "..#..",
        ".##.#",
        "#...#",
        "..#..",
    };
    std::vector<int> sizes;
    for (int r = 0; r < static_cast<int>(grid.size()); r++) {
        for (int c = 0; c < static_cast<int>(grid[r].size()); c++) {
            if (grid[r][c] == '.') {
                sizes.push_back(fill_count(grid, r, c));
            }
        }
    }
    for (int size : sizes) {
        std::cout << "region of " << size << " cells\n";
    }
}

Output:

region of 3 cells
region of 10 cells

Exercise 5: Print a list in reverse with a stack

Use an explicit stack to print the numbers 3, 1, 4, 1, 5 in reverse order.

Show the answer

Push the numbers in their original order. The last number pushed is on the top, so popping them prints the list backwards.

C++ · editable

Output:

5 1 4 1 3

The output ends with a space before the newline, because the loop prints a space after each number.

Summary

The call stack has a fixed size, and deep recursion can crash the program. An explicit stack lives in the heap, which is limited by the machine's memory instead.
A stack is last in, first out. Use push_back, back, pop_back and empty on a std::vector to build one.
Replace each recursive call with an item pushed onto the stack, and run a while loop until the stack is empty.
Mark a cell when it is pushed, not when it is popped, so each cell enters the stack only once.
Check empty() before reading the top, and check the row and column before indexing the grid.
The explicit stack fills the same cells as the recursive version, but it may visit them in a different order.

Explicit stack

Why it matters

What the call stack does

Building the stack yourself

The problem: flood fill

The recursive version

Worked example 1: the same fill with a loop

Worked example 2: tracing the stack

Worked example 3: a grid too big for recursion

Improving the stack: mark a cell when it is pushed

Common mistakes

Popping from an empty stack

Checking the bounds after indexing

Forgetting to mark the cell

Expecting the same visit order

Practice

Exercise 1: The visit order on a 2 by 2 grid

Exercise 2: Return the number of cells filled

Exercise 3: Why marking on push keeps the stack small

Exercise 4: Sizes of every region

Exercise 5: Print a list in reverse with a stack

Summary

Stuck? Ask the tutor