Функция рекурсивного заполнения запустила ошибку переполнения стека (иногда) - PullRequest
Новая
       23

Функция рекурсивного заполнения запустила ошибку переполнения стека (иногда)

0 голосов
/ 26 июня 2018

В качестве упражнения я реализовал простой редактор пикселей. Одним из режимов является заливка, которая использует рекурсивное решение. Он работает без проблем с размерами сетки менее 40x40 пикселей. Однако при тестировании на больших размерах сетки (например, 64x64) будет закрыта только часть платы, на консоли будет отображаться ошибка Uncaught RangeError: Maximum call stack size exceeded. Это, конечно, указывает на то, что жестко заданный размер стека вызовов для данного браузера был превышен. Для Chrome есть проблема для 64x64. Для Firefox нет.

Я удивлен, что то, что я считал простой реализацией заливки, приводит к такой ошибке, которая заставляет меня думать, что я сделал что-то не так. Добавление к путанице является тот факт, что ошибка не генерируется последовательно в Chrome. Позвольте мне объяснить - когда я впервые открываю веб-страницу, содержащую мое приложение, и пытаюсь выполнить заливку, ошибка генерируется всегда Когда я очищаю доску (устанавливая все ячейки div на «белый») и снова пытаюсь выполнить функцию заливки, доска обычно заполняется полностью просто отлично.

Во время работы над проблемой я также включил переменную-счетчик внутри функции floodFill с шагом, равным единице, каждый раз, когда вызывается функция. Для первого запуска (который приводит к сбою) он получает значение около 4000. После очистки доски и повторной попытки она достигает около 16 000, и доска полностью заполняется. Это, кажется, рассеивает всякое представление о том, что то, как я очищаю доску, уменьшает глубину рекурсии.

Итак ... 1) Есть идеи, что здесь происходит? и 2) плохо ли я написал свой алгоритм?

Предполагая, что я либо ошибся с моим алгоритмом, я все же хотел бы знать ответ на 1). Почему результаты кажутся недетерминированными. 

 function floodFill(xCoordinate, yCoordinate, fillColor, regionColor) {

    //checks to make sure that there is a cell at the specified coordinate
    if(!(row[yCoordinate] && row[yCoordinate][xCoordinate])) {
        return
    }   
    //checks if cell is already filled with the appropriate color
    else if(row[yCoordinate][xCoordinate].style.backgroundColor === fillColor) {
        return
    }
    //checks to see if this cell is apart of the region that is SUPPOSED to be colored
    else if(row[yCoordinate][xCoordinate].style.backgroundColor !== regionColor) {
        console.log("nope: not fill region");
        return
    }

    //changes the color of the current cell if the above conditions don't triger a return
    brush.prototype.changeCellColor(xCoordinate, yCoordinate);

    //creates a variable storing the displacment vectors that specify which cells to check next
    var coordinates = [
        [0, -1],
        [1, 0],
        [0, 1],
        [-1, 0]
    ];

    // recursivley runs the floodFill function of each of the cells specified by the displacement vectors
    coordinates.forEach(function(element){
        floodFill(xCoordinate + element[0], yCoordinate + element[1], fillColor, regionColor);
    });
}
...