JavaScript递归函数不停止执行

Question

在我的progress函数中，它将到达递归的底部，但是我期望返回的值没有改变。

let graph = [[1,1,1],[1,1,1,],[1,1,1]]

function findPath(graph){
    function progress(row, col){
        if(row == graph.length-1 && graph[row][col]== 1) {
            console.log('makes it here but does not return true !?')
            return true;
        } 

        //check right
        if(graph[row][col+1] == 1) {
            graph[row][col] = 2
            progress(row, col+1);
        }

        // check left 
        if(graph[row][col-1] == 1) {
            graph[row][col] = 2
            progress(row, col-1);
        }

        // check down
        if(graph[row+1][col] == 1){
            graph[row][col] = 2
            progress(row+1, col)
        }  
    }

    for(let i = 0; i < graph[0].length; i++) {
        if(graph[0][i] == 1) {
            if(progress(0, i)) {
                return true;
            }
        }
    }

    return false;
}

console.log(findPath(graph))

这应该返回true，它符合条件（记录文本），但随后继续移动，并且始终返回false。

Answer 1

好的，递归与堆栈一起工作，每个调用都是堆叠的，只是在所有其他调用完成后继续执行。

比如:

呼叫 1 -

在到达最后一个呼叫(< code>callN)后，所有呼叫将从后向前取消堆叠。

您只需在最后一次调用时返回true，但当函数调用取消堆栈时，该值将丢失

换句话说，对于您的示例作品，您需要始终从进度函数返回值。

我试图调整您的代码以更好地工作：

let graph = [[1,1,1],[1,1,1,],[1,1,1]]

function findPath(graph){
    function progress(row, col){
        if(row == graph.length-1 && graph[row][col]== 1) {
            return true;
        } 

        //check right
        if(graph[row][col+1] == 1) {
            graph[row][col] = 2
            var right = progress(row, col+1);
        }

        // check left 
        if(graph[row][col-1] == 1) {
            graph[row][col] = 2
            var left = progress(row, col-1);
        }

        // check down
        if(graph[row+1][col] == 1){
            graph[row][col] = 2
            var down = progress(row+1, col)
        }

        // propagate result
        return (right || left || down)
    }

    for(let i = 0; i < graph[0].length; i++) {
        if(graph[0][i] == 1) {
            if(progress(0, i)) {
                return true;
            }
        }
    }

    return false;
}

console.log(findPath(graph))

我只关注递归部分，而不是问题本身，在我的例子中，如果在任何路径(右，左或下)中，我获取该值并传递回来，直到它到达我的第一个函数调用。这样，< code>true值将一直传播到最后

希望我已经帮上忙了