javascript递归函数陷入无限循环

Question

我有以下递归函数，除非坐标超出 DOM 表，或者除非起点和当前递归点之间的距离大于用户给出的距离，否则该函数应该调用自身。然而，函数陷入了无限循环，在几个点之间无限切换，我不知道我做错了什么。

function fillSquare(a,b,dist){
    var xStart = parseInt(a);
    var yStart = parseInt(b);
    var distance = dist;

    function fill(c,d){
        var x = parseInt(c);
        var y = parseInt(d);

        if(x<0 || y<0 || x>boardWidth-1 || y>boardHeight-1){
            return;
        }else if(getDistance(cells[getFieldId(xStart,yStart)], cells[getFieldId(x,y)]) > dist){
            return;
        }else{
            cells[getFieldId(x,y)].hasWall = false;
            document.getElementById(x+'x'+y).backgroundColor = 'gray';
            console.log(x+' '+y);

            fill(x-1,y);
            fill(x+1,y);
            fill(x,y-1);
            fill(x,y+1);
        }
    }

    fill(xStart,yStart);
}

任何帮助将不胜感激。

Answer 1

问题在于递归调用将返回到相同的元素。例如，当您执行 fill(4, 5) 时，它会调用 fill(x-1, y)，即 fill(3, 5)。然后调用 fill(x+1, y)，返回到 fill(4, 5)。它将在它们之间不断循环。

您需要检查是否已经填充了某个元素，并且不要重复填充。

function fill(c,d){
    var x = parseInt(c);
    var y = parseInt(d);

    if(cells[getFieldId(x, y)].hasWall === false || x<0 || y<0 || x>boardWidth-1 || y>boardHeight-1){
        return;
    }else if(getDistance(cells[getFieldId(xStart,yStart)], cells[getFieldId(x,y)]) > dist){
        return;
    }else{
        cells[getFieldId(x,y)].hasWall = false;
        document.getElementById(x+'x'+y).backgroundColor = 'gray';
        console.log(x+' '+y);

        fill(x-1,y);
        fill(x+1,y);
        fill(x,y-1);
        fill(x,y+1);
    }
}