The idea: paint one cell, then ask the neighbours to do the same

The paint bucket in a drawing program fills the area you click: every cell of the same colour that it can reach without crossing another colour. The classic way to write it is a short recursion. fill(r, c) paints one cell and then calls itself on the cell's 4 neighbours: north, east, south and west.

A 3 by 3 block of cells with the middle one painted orange and labelled (r, c); next to it the four calls fill(r-1, c), fill(r, c+1), fill(r+1, c), fill(r, c-1): three white neighbours get painted and recurse, the black east neighbour returns at once
One call paints its cell, then makes 4 calls; a call on a cell of another colour returns at once.

The colour of the clicked cell is the target; the fill replaces it with a new colour. The cells show the order they were painted in (#1, #2, …). The panel on the right is the call stack: one row per call that has started but not returned yet, the newest at the bottom (orange).

The two base cases

fill(r, c):
    if (r, c) is outside the grid:  return      # base case 1
    if colour[r][c] != target:      return      # base case 2: a wall, or already painted
    colour[r][c] = new
    fill(r - 1, c)    # N
    fill(r, c + 1)    # E
    fill(r + 1, c)    # S
    fill(r, c - 1)    # W

Most calls end in a base case. Every painted cell makes 4 calls, so a fill that paints n cells makes exactly 1 + 4n calls. The square in Demo: fill a closed square has 9 white cells inside: 9 paints and 37 calls, each one shown as a step.

Why the cell is painted before the calls

Painting first is what makes the recursion stop. When the east neighbour later calls back west, that cell is no longer the target colour, so the call returns at once. Painted cells serve as the "visited" marks of a depth-first search: flood fill is a DFS on the grid, with cells as vertices and neighbours as edges.

That also explains a classic bug: if the new colour equals the target colour, painting changes nothing, every cell stays the target colour and the calls go back and forth forever. Real code checks if new == target: return first. This page always picks a different colour.

4 neighbours or 8

With 8 neighbours the fill also moves diagonally (NE, SE, SW, NW). A line drawn with diagonal steps then leaks: the fill slips between two black cells that touch only at a corner. In Demo: 4 neighbours stay in the diamond the fill paints the 5 cells inside the diamond (21 calls). In Demo: 8 neighbours leak through a diagonal the same click paints 75 cells: the inside and all 70 white cells outside.

The same diamond outline drawn with diagonal steps, twice: with 4 neighbours only the 5 inner cells turn orange; with 8 neighbours a red arrow goes diagonally between two black cells and the whole outside turns orange too
A diagonal line is a wall for a 4-way fill but has gaps for an 8-way fill.

So paint programs fill with 4 neighbours, and a boundary that must hold an 8-way fill has to be drawn 4-connected (no corner-only joins).

How deep the recursion goes

Each call waits for its 4 calls to finish, so the stack holds the whole chain of calls from the click to the current cell. In an open area that chain snakes through almost every cell. Demo: deep recursion in an open room paints the 70 cells of the room with 281 calls, and the stack reaches 71 frames.

FillExtra memoryWorst case for an image of n pixels
RecursionCall stack, one frame per unfinished callAbout n frames: 1 000 000 for a 1000 × 1000 image
Queue (BFS)A queue of painted cells whose neighbours are not checked yetThe width of the "front": a few thousand cells for the same image

A real call stack is small: Python stops at 1000 frames by default (RecursionError), and a browser at roughly ten thousand (RangeError: Maximum call stack size exceeded). Demo: stack overflow (limit 20 frames) sets the limit to 20 to show it: the program crashes with the room half painted.

The queue version: no recursion, filling in rings

The fix is to keep the cells to visit in your own queue, as in breadth-first search: paint a cell when it is added, take cells from the front, add their target-coloured neighbours at the back. The same 70 cells get painted, but in rings around the start, and the queue stays short (Demo: queue (BFS) fills in rings: at most 14 cells). An explicit stack instead of a queue works too; it paints in DFS order.

Two 6 by 4 rooms with the paint order in each cell. Left, recursion from the corner: the numbers 1 to 24 snake through the room and the stack reaches 25 frames. Right, a queue from cell (1, 2): the numbers grow in rings around the start, and the queue holds at most 8 cells
Recursion paints one long snake and keeps all of it on the stack; a queue paints in rings and keeps only the front.

Counting islands

The same fill counts connected components. Scan the grid row by row. Each land cell that is not painted yet is the first cell of a new island: add 1 to the count and flood fill the whole island, so the scan never counts it again. Demo: count islands, 4 neighbours finds 10 islands; Demo: count islands, 8 neighbours finds 8, because land that touches only at a corner now joins one island. Every cell is painted once and checked a few times, so the whole count takes time proportional to the number of cells. See also Connected Components for the same idea on a graph.

Where flood fill is used

  • The paint bucket and the "magic wand" selection in image editors.
  • Counting islands, rooms or blobs in a grid or an image (connected component labelling).
  • Minesweeper: clicking an empty square opens all the empty squares around it.
  • Go: finding a group of stones and its liberties.
  • Checking that every cell of a generated maze can be reached.

What the page leaves out

  • Scanline (span) fill, which fills a whole horizontal run per step and is what image editors use for speed.
  • Colour tolerance: real paint buckets also fill colours that are only close to the target.
  • Anti-aliased edges and filling vector shapes (polygon fill).
  • Union-find labelling, another way to count components in one pass.

See also Recursive Factorial for the call stack on the simplest recursion, and Depth-First Search for the same search on a graph.