A recursive function stuck in an endless loop, going on indefinitely

Question

A recursive function stuck in an endless loop, going on indefinitely

I have a recursive function that is supposed to call itself until the coordinates exceed the boundaries of a DOM table or until the distance between the starting point and the current recursion point is greater than the user-defined distance. However, the function seems to be stuck in an infinite loop, constantly switching between several points and I can't seem to pinpoint what went 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<span class="operator"><</span>0 || y<span class="operator"><</span>0 || x<span class="operator">></span>boardWidth-1 || y<span class="operator">></span>boardHeight-1){
            return;
        }else if(getDistance(cells[getFieldId(xStart,yStart)], cells[getFieldId(x,y)]) <span class="operator">></span> 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 assistance on this matter would be highly appreciated.

javascript recursion

Answer 1

Answer №1

The issue arises from the recursive calls repeatedly returning to the same elements. For example, a call to fill(4, 5) leads to fill(3, 5), then fill(4, 5) again, creating an endless loop between them.

To resolve this problem, it is important to implement a check to see if an element has already been filled to prevent repetition.

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

Answer 2

The issue arises from the recursive calls repeatedly returning to the same elements. For example, a call to fill(4, 5) leads to fill(3, 5), then fill(4, 5) again, creating an endless loop between them.

To resolve this problem, it is important to implement a check to see if an element has already been filled to prevent repetition.

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

Answer 3

Answer №2

Unfortunately, without access to the remaining code, could you please provide the console output for the following:

// Debugging purposes
var i = 0;

// Helper function for converting into integers
function fillSquare(xStart, yStart, distance)
{
    // Initialization
    // The first run uses start as current
    fill(parseInt(xStart), parseInt(yStart), parseInt(xStart), parseInt(yStart), distance);
}

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

    // Logging current 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 again since it was done in the initial run and the recursive calls rely on 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)
    }
}

Answer 4

Unfortunately, without access to the remaining code, could you please provide the console output for the following:

// Debugging purposes
var i = 0;

// Helper function for converting into integers
function fillSquare(xStart, yStart, distance)
{
    // Initialization
    // The first run uses start as current
    fill(parseInt(xStart), parseInt(yStart), parseInt(xStart), parseInt(yStart), distance);
}

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

    // Logging current 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 again since it was done in the initial run and the recursive calls rely on 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)
    }
}

A recursive function stuck in an endless loop, going on indefinitely

Answer №1

Answer №2

Similar questions

Leverage the variables' values to access property

Emphasize the cell in the initial column to indicate the resulting or winning selection

Establishing the variable for the input value attribute with a space included

Having trouble transmitting JSON data to an Express server through the browser

Adjust the hue of a single side of the cube with THREE.js

The CSS I've written isn't functioning properly within a div that was generated using

Is there a way for me to enable autoplay on the Slice Slider?

jQuery Autocomplete with Link Options

Vue.js error: Trying to access an undefined property

What is the process of converting an arrow function into an asynchronous one?

Modify the filtered class of ng-repeat using the $index value from the controller

The JavaScript function prints the variable using `console.log(var)`, however, it does not assign `var2` to

Guide to loading JQuery in an electron webview using a proxy

Transform a String into an Array object

Exploring Angular.js methods to capture values from check boxes and radio buttons simultaneously

Error: Unable to access attribute 'item_name' as it is not defined

When the affirmative button is clicked, apply a border and background color

Whenever a new entry is made into the textfield, the onChange feature triggers a reset on the content within the textfield

Creating relationships in Sequelize.js: Linking a model using two keys from another model

Discover the Mongoose Document and Arrange in a Random Order with Various Levels?