javascript - 递归洪水填充函数触发堆栈溢出错误（有时）

Question

作为练习，我实现了一个简单的像素编辑器。其中一种模式是使用递归解决方案的洪水填充。它适用于小于大约 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);
    });
}

标签： javascripthtmlstack-overflowflood-fill