Explicit stack in Python

Why this matters

Recursion is the clearest way to write many programs, but it has a limit. Each call to a function uses some memory on the call stack, and Python allows only a fixed number of waiting calls, which is 1000 by default. A program that calls itself too many times stops with a RecursionError. A flood fill on a large picture can call itself once for each pixel it paints, so a correct recursive program can still reach that limit.

The fix is to write the same work as a loop, and to keep a list of the work still to do in your own data structure. That data structure is called an explicit stack. It holds the same kind of information the call stack holds, but it lives in ordinary memory, as a list, and a loop works through it. That memory is far larger than the call stack's fixed limit, so the limit is set by the total memory available, not by a fixed depth.

This lesson uses a flood fill as the example. The recursive version of flood fill is covered in the flood fill lesson of this module, so this lesson only shows the code it needs. The Towers of Hanoi lesson, which comes just before this one, uses recursion without a loop.

Words used in this lesson

A stack is a collection where you add an item to the top and take an item from the top. The usual names are push for adding and pop for taking. A stack is last in, first out, written LIFO. The last item you pushed is the first one you pop.

Pending work means work you have found but not yet done. A recursive call is pending work: the function has started and is waiting for the inner call to finish. An explicit stack stores the pending work as data.

A grid is a table of rows and columns. In Python, a grid is a list of rows, and each row is a list of numbers. The value grid[r][c] is the number in row r and column c. Rows and columns count from 0.

A neighbour of a cell is a cell directly above, below, left or right of it. Diagonal cells are not neighbours in this lesson.

Flood fill changes the colour of a region. You give it a start cell and a new colour. It changes the start cell and every cell connected to it through neighbours that have the same old colour.

In Python, a plain list works well as a stack. The method append is the push, and pop() takes the last item. The collections module also has deque, which can add and remove items at either end. This lesson uses a list.

What the call stack does

Before you replace recursion, look at what it does. Here is a small function that calls itself.

def depth(n: int) -> int:
    if n == 0:
        return 0
    return 1 + depth(n - 1)

Call depth(3). The call cannot finish yet, because it needs the value of depth(2). So the call waits. depth(2) needs depth(1), which needs depth(0). Now depth(0) returns 0 at once. The waiting calls finish in reverse order. depth(1) returns 1 + 0, which is 1. depth(2) returns 1 + 1, which is 2. depth(3) returns 1 + 2, which is 3.

Each waiting call is a frame on the call stack. A frame holds the function's inputs and any values it is still waiting on. Python pushes a frame for each call and pops it when the call returns. This is the last-in, first-out behaviour the rest of the lesson uses.

Where recursion runs out

The call stack has a fixed limit, which is the recursion limit from the first lesson. Run this program to see the limit in action.

The output is:

900
RecursionError

The first call finishes, because 900 calls fit under the limit of 1000. The second call asks for 100 million waiting frames, which does not fit. Python stops that call with RecursionError. The try and except lines catch the error, so the program can print a message and continue. Without them, Python would print a traceback with the same line repeated many times, and then stop.

An explicit stack avoids this limit. Its items are stored in a list, and a loop pops one item at a time, so the call stack does not grow.

The idea: a loop with its own stack

The explicit-stack version has three parts.

1. A stack that holds the work still to do. At the start it holds the first piece of work.
2. A loop that runs while the stack is not empty.
3. In each pass, the loop pops one item, does the work for it, and pushes any new work that item creates.

The loop replaces the calls. The stack replaces the waiting frames. Nothing in the code calls itself, so the call stack never grows.

To see how the stack works, run a program with three pushes and three pops.

Example 1: last in, first out

This program pushes 1, 2 and 3, then pops until the stack is empty.

The output is:

Size after three pushes: 3
Popped 3
Popped 2
Popped 1

The values come out in reverse order. The last value pushed, 3, is the first one popped. The list[int] in the first line is a type hint, which names the kind of items the list holds. The append and pop methods both work at the same end of the list, which is what makes it a stack. The while stack: line is true as long as the list has at least one item, because an empty list counts as false.

Example 2: flood fill, both ways

Here is a grid. The digits are colours. The 1s form a region that touches the top-left cell.

1 1 0 1
1 0 0 1
1 1 1 0
0 0 1 1

A flood fill from the top-left cell with new colour 2 changes every 1 that is connected to that cell. The 1s in the top-right corner are not connected, because the 0s between them block the way, so they stay 1.

The recursive version checks the start cell, paints it, and then calls itself on each of the four neighbours. If a neighbour is outside the grid or has a different colour, the call returns at once.

The explicit-stack version does the same work with a loop. It pushes the start cell. Then it repeats these steps until the stack is empty: pop a cell, check it, paint it if it matches, and push its four neighbours.

This program runs both versions on copies of the same grid, and then runs the stack version with the same new colour as the old one. The grid is a list of lists, so the function changes the cells in place.

The output is:

Recursive:
2 2 0 1
2 0 0 1
2 2 2 0
0 0 2 2
Explicit stack:
2 2 0 1
2 0 0 1
2 2 2 0
0 0 2 2
Same colour, no change:
1 1 0 1
1 0 0 1
1 1 1 0
0 0 1 1

The two fills give the same grid. The loop version never calls itself, so it does not need the call stack for each cell. The continue statement skips to the next pass of the loop. Here it means "this popped cell is not useful, go to the next one."

The tuple (start_r, start_c) holds a row and a column together. The line r, c = stack.pop() unpacks the tuple into two names in one step.

Look at the bounds check, which tests that the row and column are inside the grid. It comes before grid[r][c] is read, because the check decides whether the index is valid. The mistakes section shows what happens when the order is reversed.

The third call starts on a cell that already has the new colour. The if old == new line returns at once. Without that line, the loop would not stop, as the mistakes section explains.

The fill finds every connected cell, and the order in which it paints them may differ from the recursive version. The final grid is the same in both cases, because both versions paint every cell reachable from the start through cells of the old colour.

Example 3: following the stack one step at a time

Example 2 shows the result, but not the steps. This program uses a 2 by 2 grid, small enough to follow by hand. It prints each pop, and after each painted cell it prints the cells still waiting in the stack, with the top first. The top of a Python list is its last item, so the program prints the list in reverse.

The output is:

Step 1: pop (0,0) paint it 2
  waiting, top first: (0,1) (0,-1) (1,0) (-1,0)
Step 2: pop (0,1) paint it 2
  waiting, top first: (0,2) (0,0) (1,1) (-1,1) (0,-1) (1,0) (-1,0)
Step 3: pop (0,2) outside the grid, skip
Step 4: pop (0,0) value 2, skip
Step 5: pop (1,1) paint it 2
  waiting, top first: (1,2) (1,0) (2,1) (0,1) (-1,1) (0,-1) (1,0) (-1,0)
Step 6: pop (1,2) outside the grid, skip
Step 7: pop (1,0) value 0, skip
Step 8: pop (2,1) outside the grid, skip
Step 9: pop (0,1) value 2, skip
Step 10: pop (-1,1) outside the grid, skip
Step 11: pop (0,-1) outside the grid, skip
Step 12: pop (1,0) value 0, skip
Step 13: pop (-1,0) outside the grid, skip

Step 1 pops the start cell and paints it. The four neighbours are pushed in the order up, down, left, right. The last one pushed, the right neighbour, is on top, so it is the next cell popped. Step 2 paints that cell, and its four neighbours go on top of the others.

Steps 3 and 4 show the two kinds of skip. Cell (0,2) is past the last column, so it fails the bounds check. Cell (0,0) is inside the grid, but it already has the new colour 2, so it does not match the old colour 1 and is skipped. Step 5 paints the cell below step 2's cell, which is (1,1). The rest of the steps are skips.

Three cells are painted, and the loop takes 13 pops to finish. Most of the pops are for neighbours that were pushed but could not be painted. This is the reason the stack can be larger than the number of cells, which the next example measures.

Example 4: how big the stack gets

The stack holds pending work. The number of items it holds at one time is a useful measure of the memory the fill needs. This program changes the stack version to record the largest size it reaches, and it returns that size.

The output is:

Largest pending size on a 10 by 10 empty grid: 238
Largest pending size on the 4 by 4 grid: 16

The 10 by 10 grid has 100 cells, but the largest stack size is 238. The reason is that every painted cell pushes four entries, one for each neighbour. Many of those entries point outside the grid or to cells that are already painted. They are not discarded when they are pushed. They wait in the stack until they are popped and then skipped. So the stack can hold more entries than there are cells.

This is the cost of the explicit stack. Memory use depends on how many entries are waiting, not only on how many cells there are. A version that checks each neighbour before pushing it would keep the stack smaller, at the cost of a few more checks. The version here is simpler to read, and it is correct.

The grid in the program is 10 by 10, which is small. The same code on a grid of a million cells would hold a larger stack, and it would still use only ordinary memory. The recursive version could fail on a grid that large, because its depth of calls can reach the number of painted cells, and Python stops at 1000 unless the limit is raised.

Common mistakes

Reading the grid before the bounds check. If grid[r][c] runs before the r < 0 check, a cell at the edge of the grid can cause a wrong answer or an error. Python is the trap here. A negative index does not fail. It counts from the end of the list. Here is a short program that reads column -1 of the first row:

The output is:

1

No error appears, and the number is wrong for a flood fill. Column -1 is the last column of the row, which is a different cell from the one the search meant to check. Reading past the other end of the row raises an error instead:

The output ends with:

IndexError: list index out of range

Put the bounds check first, as in the code above, so that the index is known to be valid before the grid is read.

Forgetting the same-colour guard. If the old colour and the new colour are the same, every painted cell still matches the old colour. Each pop pushes four neighbours, and those neighbours match too. The stack never becomes empty, so the loop never ends and the list keeps growing until the computer runs out of memory. The guard if old == new stops this before the loop starts. The next program has the guard removed. It is run under timeout 3, so it stops after three seconds. The done line never prints. The timeout command stops the program after three seconds with exit code 124, or Python raises MemoryError first if the list fills the memory:

DR = [-1, 1, 0, 0]
DC = [0, 0, -1, 1]
 
 
def fill_no_guard(grid: list[list[int]], sr: int, sc: int, new: int) -> None:
    old = grid[sr][sc]
    stack = [(sr, sc)]
    while stack:
        r, c = stack.pop()
        if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]):
            continue
        if grid[r][c] != old:
            continue
        grid[r][c] = new
        for d in range(4):
            stack.append((r + DR[d], c + DC[d]))
 
 
fill_no_guard([[1, 1], [1, 1]], 0, 0, 1)
print("done")

Painting at the wrong time. This code paints a cell when it is popped. If you paint when a cell is pushed, you must check the colour before pushing too. Otherwise the same cell is pushed many times and the work repeats. Choose one rule and keep it.

Using pop when you meant to look at the top. pop() removes the item. If you need the top item without removing it, read stack[-1]. Removing it by mistake means the next pass of the loop sees a different cell.

Expecting the same visiting order as the recursive version. The final grid is the same, but the order in which cells are painted can differ. Do not write a test that checks the order unless you have checked the order you want.

Practice

Exercise 1

The program pushes 5, then 6. It pops once, pushes 7, then pops until the stack is empty. In what order are the values popped after the first push of 5?

Show the answer

It pops 6 first, then 7, then 5. The stack holds 5 and 6 with 6 on top. The pop removes 6. Then 7 is pushed on top of 5, so the next pop removes 7, and the last pop removes 5.

Exercise 2

Change fill_stack in Example 2 so that it returns the number of cells it painted. For the 4 by 4 grid, what number does it return?

Show the answer

Add a counter that starts at 0 and goes up by one each time grid[r][c] = new runs, then return the counter. The output of Example 2 has eight cells with the value 2 after the fill, and each of those was painted once. So the answer is 8.

Exercise 3

Explain in your own words why the recursive fill and the stack fill paint the same set of cells, even though they visit cells in a different order.

Show the answer

Both versions start at the same cell and move only to neighbours that have the old colour. They keep going until no reachable neighbour is left. The order changes which cell is checked first, but every reachable cell is eventually checked and painted, so the set of painted cells is the same.

Exercise 4

What does fill_stack do on a grid [[5]] when it starts at row 0, column 0 with new colour 5?

Show the answer

It does nothing. The start cell already has the new colour, so the guard if old == new returns at once, and the grid stays [[5]].

Exercise 5

Write the code that pushes the four neighbours of cell (r, c) in the order up, down, left, right. Use the lists DR and DC.

Show the answer

Use a loop with for d in range(4): and call stack.append((r + DR[d], c + DC[d])) inside it. The lists give the offsets for up, down, left and right in that order, so the four pushes match the description.

Summary

• A recursive call uses a frame on the call stack, and Python's recursion limit, 1000 by default, caps how deep recursion can go.
• An explicit stack is a loop with a list of pending work, so the limit is the memory available, not a fixed depth.
• A Python list with append and pop() is a stack.
• The flood fill loop pops a cell, checks it, paints it, and pushes its four neighbours, with a bounds check before the grid is read.
• The stack can hold more entries than there are cells, because neighbours are pushed before they are checked.
• A guard for the case where the old and new colours match is needed, or the loop does not end.
• A negative index in Python does not raise an error, so put the bounds check before every read.