javascript recursive function does not stop execution

Question

Inside of my progress function, it will hit the base of the recursion, but the value im expecting to have returned does not change.

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))

This should return true, it hits the condition (logs the text) but then keeps moving, and always returns false.

Note, you need to add a return before each recursive call to progress(). — Shidersz
– Shidersz, Commented May 9, 2019 at 17:56
I guess 1 marks a valid "step" along the path? Instead of a graph of all 1s, maybe you should show some other inputs and their expected outputs? — Mulan
– Mulan, Commented May 9, 2019 at 17:59

igornfaustino · Accepted Answer · 2019-05-09 18:47:54Z

Ok, recursion works with an stack, each call is stacked and just continues your execution after all the other call stacked after are done.

Like:

call1 -> call2 -> call3 -> callN

after reach the last call (callN), all the calls will be unstacket from back to front.

You just return true on the last call, but this value get lost when the function calls is unstacked

In other words, to your example works, you need to always return the value from the progress function.

I tried to adapty your code to work better:

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))

I only look to the recursion part, and not for the problem it self, in my example, if in any path (right, left or down) i grab that value and pass back untill it reach my first function call. That way, the true value will be propagate until the end

Hope i have helped

Collectives™ on Stack Overflow

javascript recursive function does not stop execution

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related