javascript recursive function falling in infinite loop

Question

I have following recursive function which should call itself unless coordinates goes beyond DOM table or unless distance between starting point and point of current recursion is greater than distance given by user. However function falls into infinite loop switching infinitely between several points and I can't figure out what I have done wrong.

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

Any help will be greatly appreciated.

You have a function within a function. Do you mean to do that? — Matt Cremeens
– Matt Cremeens, Commented Jun 3, 2016 at 19:47
@Matt Cremeens Yes. xStart and yStart should have same value during whole process (so inner fill function can compare starting point (with coordinates xStart and yStart) and point after n-th recursion and return distance between them. I have no idea how to do that in different way. — Furman
– Furman, Commented Jun 3, 2016 at 19:52
@Iven Yes I think so... my goal was to make flood fill algorithm with additional condition... — Furman
– Furman, Commented Jun 3, 2016 at 19:54
It looks like you might just be running into some off-by-one errors in your first if statement. Have you tried taking away the -1 to boardWidth and boardHeight? — Brice
– Brice, Commented Jun 3, 2016 at 19:55
I don't understand - fill(x,y+1); will be called again by the recursive fill(x,y-1); call and vice versa. There are tons of multiple calls. This function is just wrong in so many ways — Alon Eitan
– Alon Eitan, Commented Jun 3, 2016 at 20:00

Barmar · Accepted Answer · 2016-06-03 20:59:45Z

The problem is that the recursive calls will go back to the same elements. For instance, when you do fill(4, 5), it calls fill(x-1, y), which is fill(3, 5). Then that calls fill(x+1, y), which goes back to fill(4, 5). It will keep cycling between them.

You need to check whether you've already filled an element, and not repeat it.

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

IMTheNachoMan · Accepted Answer · 2016-06-03 20:08:53Z

Since I don't have the rest of your code, what is the console output of this:

// for debugging
var i = 0;

// helper function to parse into integers
function fillSquare(xStart, yStart, distance)
{
    // kick it off
    // on the first run the current is the start
    fill(parseInt(xStart), parseInt(yStart), parseInt(xStart), parseInt(yStart), distance);
}

function fill(xCurrent, yCurrent, xStart, yStart, distance)
{
    // the next two lines are temporary just for debugging purposes
    ++i;
    if(i > 100) return;

    // log where we are so we can see progress
    console.log({ "xCurrent" : xCurrent, "yCurrent" : yCurrent, "xStart" : xStart, "yStart" : yStart, "distance" : distance, "getDistance" : getDistance(cells[getFieldId(xStart,yStart)], cells[getFieldId(xCurrent, yCurrent)]) });

    // no need to parse since you did that on the initial run and the recursive calls are all basic math

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

        fill(xCurrent - 1, yCurrent, xStart, yStart, distance)
        fill(xCurrent + 1, yCurrent, xStart, yStart, distance)
        fill(xCurrent, yCurrent - 1, xStart, yStart, distance)
        fill(xCurrent, yCurrent + 1, xStart, yStart, distance)
    }
}

Collectives™ on Stack Overflow

javascript recursive function falling in infinite loop

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related