在 Javascript 中结束递归

Question

所以我尝试在js中实现floodfill算法，并提出了以下内容：

function floodAreaFromPoint(x,y) {
    if(typeof pixel[x] == "undefined") pixel[x] = [];
    pixel[x][y] = 1; // 1 for alpha
    if(!coordsInPixelArray(x + 1,y)) floodAreaFromPoint(x + 1,y);
    if(!coordsInPixelArray(x,y + 1)) floodAreaFromPoint(x,y + 1);
    if(!coordsInPixelArray(x - 1,y)) floodAreaFromPoint(x - 1,y);
    if(!coordsInPixelArray(x,y - 1)) floodAreaFromPoint(x,y - 1);
}

它工作得很好，但我在填充更大的区域（10000x10000）时遇到了一些问题，其中这个 alogrithm 会导致错误"超出最大调用堆栈"。我理解此错误的含义，但我不知道如何解决此问题...

我愿意用更有效的算法替换这个函数，但我认为这个问题的解决方案可能是结束递归（我不知道如何在 js 中正确实现）。

编辑：像素数组包含应填充的像素。调用函数时，它已经包含所有边框像素。

溶液：

function flood(x,y) {
    var nodes = [];
    nodes.push({"x":x,"y":y});
    while(nodes.length > 0) {
        var p = nodes[nodes.length - 1];
        if(coordsInPixelArray(p.x, p.y)) {
            nodes.pop();
            continue;
        }
        if(typeof pixel[p.x] == "undefined") pixel[p.x] = [];
        pixel[p.x][p.y] = 1; // 1 for alpha
        if(!coordsInPixelArray(p.x + 1, p.y)) nodes.push({"x": p.x + 1,"y": p.y});
        if(!coordsInPixelArray(p.x - 1, p.y)) nodes.push({"x": p.x - 1,"y": p.y});
        if(!coordsInPixelArray(p.x, p.y + 1)) nodes.push({"x": p.x,"y": p.y + 1});
        if(!coordsInPixelArray(p.x, p.y - 1)) nodes.push({"x": p.x,"y": p.y - 1});
    }
}

Answer 1

解决方案非常简单：删除递归。您也可以使用堆栈并将节点推送到堆栈，而不是递归调用。伪代码：

stack nodes//create a new stack
add(nodes , startNode)//initialize the stack with the first node
while ! isEmpty(nodes)//still nodes available that haven't been processed
    node p = peek(nodes)
    if ! nodeInArray(p) OR getColor(p) == 1
        //this node has already been visited or is not in the array
        //continue with the next node in the stack
        pop(nodes)
        continue
    color(p , 1)//mark the node as visited
    push(nodes , node(x(p) - 1 , y(p))//add node to be processed in the future
    ...//push all other neighbours to the stack