Без стека: заливка, которой хватает 16 цветов

A Stackless Floodfill Automaton

Nils M Holm показывает, как обойтись без стека при заливке области: состояния конечного автомата кодируются прямо в пикселях изображения с помощью 16 запасных цветов. Стрелки в каждом пикселе хранят направление к родителю и следующее направление обхода, а при отсутствии вариантов алгоритм откатывается назад. Сложность остаётся линейной, O(4n). Подход пригодился в текстовом сапёре на BASIC с 7 КБ памяти и 30 уровнями вложенности подпрограмм.