Стек
При вызове функции копия множества переменных, которые нужны ей для работы, сохраняется в памяти. Если функция вызывается рекурсивно, то другая копия всех этих переменных сохраняется в памяти, затем еще одна и т.д. Эти копии переменных сохраняются в так называемом стеке. Первая копия находится внизу, следующая поверх нее, и т.д. К сожалению, существует ограничение на размер стека. В большинстве браузеров этот предел определен где-то в районе 1000. Это означает, что для функции заливки сетка могла бы содержать до 1000 квадратов. Некоторые браузеры имееют меньший размер стека. Web-браузер Safari, например, имеет максимальный размер стека, равный примерно 100, поэтому даже небольшая сетка 10 х 10исчерпает возможности браузера.
Таким образом мы имеем ограничение в самом браузере, которое определяет, что при использовании рекурсии можно углубиться только на 1000 уровней. К сожалению, наш алгоритм floodFill (заливки) будет в худшем случае углубляться на 1000 уровней на сетке, содержащей только 1000 полей. Если имеется что-то более сложное, то существует вероятность, что произойдет переполнение стека и просто остановка выполнения кода. Очевидно, что существуют ситуации, когда необходимо закрасить область, содержащую более 1000 пикселей. Что делать в таком случае? Попробуем изменить подход.
Прежде всего попробуем изменить алгоритм. Существует много различных алгоритмов закраски - мы использовали один из самых простых. Он проверяет все направления и затем закрашивает каждый просмотренный квадрат, если это будет необходимо. С помощью небольшого изменения можно существенно улучшить этот алгоритм, с точки зрения необходимого пространства стека. Вместо просмотра влево и вправо на 1 квадрат, можно просматривать влево и вправо на максимально возможное количество позиций и закрашивать каждый пиксель в этом направлении. Это называется алгоритмом закрашивания со сканированием по линиям, который оказывается одним из наиболее эффективным существующих алгоритмов закрашивания. К сожалению, он все еще имеет свои ограничения, и для достаточно большой области закрашивания он также может переполнять стек.
Если это произойдет, то остается единственный вариант: не использовать рекурсию. Вместо использования стека JavaScript можно создать свой собственный с помощью простого массива JavaScript. Так как массив не имеет ограничений на количество элементов массива, то можно получить "бесконечно" большой стек, которым мы управляем самостоятельно.
