Flood Fill рекурсивное переполнение стека

Question

Flood Fill рекурсивное переполнение стека

Если я пытаюсь заполнить прямоугольник 100×100, то я получаю переполнение.
А 50х50 отлично работает.

Есть ли способ исправить переполнение?

Я также распечатываю номер стека, и иногда рабочий прямоугольник стека выше, чем большой (он падает около 7000).

void draw(int x, int y)
{
if ((x >= 0 && x < 100) && (y >= 0 && y < 100))
{
canvas.set_pixel(x, y);
if (!canvas.get_pixel(x, y + 1))draw(x, y + 1);
if (!canvas.get_pixel(x, y-1))draw(x, y - 1);
if (!canvas.get_pixel(x - 1, y))draw(x - 1, y);
if (!canvas.get_pixel(x+1, y))draw(x + 1, y);

}

return;
}

0

c++fill recursion stack stack-overflow

Решение

Другие решения

Причина переполнения стека в том, что рекурсия идет слишком глубоко.

Насколько глубоко это пойдет? Ну, с алгоритмом, как вы его спроектировали — он на самом деле будет углубляться 100*100=10,000!

Давайте посмотрим, в каком порядке будет заполнен холст — предполагая, что холст пуст, и мы начинаем заполнение с середины:

установить средний пиксель
перейти к х, у + 1
делай это, пока не доберешься до края
на краю — перейти к х-1,0 (помните, мы наверху)
опуститься до самого дна

и т. д.

Суть в том, что вы идете все глубже и глубже, пока не заполните холст, а затем у вас есть «цепочка» рекурсивных вызовов, проходящих по всему холсту, и это пустая трата 🙂

Бенджамин прав, что вы можете использовать стек, но стек в основном делает то же самое (только без рекурсии), поэтому стек также достигнет глубины 10 000. Все еще пустая трата, и в некоторых случаях вам не хватает памяти (для растрового холста каждый пиксель занимает 1 бит, но стек будет иметь 2 целых числа на пиксель для x,yи, следовательно, может занять в 64 раза больше памяти, чем холст)

Вместо этого — используйте очередь! Почти тот же код:

void draw(int x, int y)
{
struct coordinate { int x, y; };
std::queue<coordinate> to_draw; // <- changed from stack to queue
to_draw.push({x, y});

while (!to_draw.empty())
{
auto top = to_draw.front(); // <- changed from top to front
to_draw.pop();
if (  (top.x >= 0 && top.x < 100)
&& (top.y >= 0 && top.y < 100)
&& !canvas.get_pixel(top.x, top.y))
{
canvas.set_pixel(top.x, top.y);
to_draw.push({top.x, top.y + 1});
to_draw.push({top.x, top.y - 1});
to_draw.push({top.x + 1, top.y});
to_draw.push({top.x - 1, top.y});
}
}
}

И теперь нужная память будет <=4*100! Другими словами — переходя от стека к очереди, мы меняли необходимую память с N*N в 4*N,

2

Источник

Accepted Answer

Не используйте рекурсию. Вместо этого используйте стек для хранения координат, которые вы хотите нарисовать. И повторять, пока стек не станет пустым.

void draw(int x, int y)
{
struct coordinate { int x, y; };
std::stack<coordinate> to_draw;
to_draw.push({x, y});

while (!to_draw.empty())
{
auto top = to_draw.top();
to_draw.pop();
if (  (top.x >= 0 && top.x < 100)
&& (top.y >= 0 && top.y < 100)
&& !canvas.get_pixel(top.x, top.y))
{
canvas.set_pixel(top.x, top.y);
to_draw.push({top.x, top.y + 1});
to_draw.push({top.x, top.y - 1});
to_draw.push({top.x + 1, top.y});
to_draw.push({top.x - 1, top.y});
}
}
}

2