Function with recursion is causing stack overflow

Question

I am having a problem with my function made to find a path in a maze of 1s and 0s, return true if it is on that path or has found the exit, and return false if the maze is unsolvable. I am getting a stack overflow error any time I try checking for the "- 1s" of my variables but my base cases should be preventing that. Is there a way to use less stack space with recursion? Here is my code

bool Pathfinder::check(string& maze, stack<string>& path, int x, int y, int z) 
{int checking = 0;
    if ((x == 4) && (y == 4) && (z == 4))
    {
        path.push(this->createCoords(x, y, z));
        return true;
    }
    else
    {
        if ((x + 1) < 1 || (x + 1) > columns)
        {
            return false;
        }
        if ((y + 1) < 1 || (y + 1) > rows)
        {
            return false;
        }
        if ((z + 1) < 1 || (z + 1) > floors)
        {
            return false;
        }
        if ((x < 0) || (y < 0) || (z < 0))
        {
            return false;
        }
        if (this->getValue(maze, x, y, z) == 1)
        {
            this->setValue(maze, x, y, z, 2);
        }
        else
        {
            return false;
        }
    }


    if (this->check(maze, path, x + 1, y, z) ||
        this->check(maze, path, x, y + 1, z) ||
        this->check(maze, path, x, y, z + 1))
    {
        checking++;
    }
    if (this->check(maze, path, x - 1, y, z) && checking == 1) //Overflow error comes from here
    {
        checking++;
    }
    if (this->check(maze, path, x, y - 1, z) && checking == 2)
    {
        checking++;
    }
    if (this->check(maze, path, x, y, z - 1) && checking == 3)
    {
        path.push(this->createCoords(x, y, z));

        return true;
    }

    return false;
}

It sounds like your function never stops recursing. Have you considered using a debugger to trace through the code or adding some logging so you know what's actually happening? — Retired Ninja
– Retired Ninja, Commented Oct 20, 2017 at 2:11
This isn’t the problem, but the first five if statements have way too many parentheses. You don’t need any of the inner ones. — Pete Becker
– Pete Becker, Commented Oct 20, 2017 at 2:14
Is there a way to use less stack space with recursion? -- So far you haven't demonstrated that the problem is stack space. What if it is just a bug in your code or a mistake in your logic that is causing the stack overflow, and not just that you a big maze? Also, what data have you tested this with? If you haven't done so, I suggest you use a much smaller maze, so to make sure this isn't just a bug. — PaulMcKenzie
– PaulMcKenzie, Commented Oct 20, 2017 at 2:17
Even without laboriously stepping through a debugger, there's a simple technique to find recursion bugs. 1) Add a Recursion Level to the argument list. 2) Update recursion calls accordingly. 3) Output Recursion Level and key information at the start of the function. (In this case x, y, z is ideal.) ... Use this technique and your bug should stick out like a sore thumb. — Disillusioned
– Disillusioned, Commented Oct 20, 2017 at 3:08

Sam Varshavchik · Accepted Answer · 2017-10-20 02:30:09Z

You cannot use "less stack space" for the simple reason that when the amount of required stack space is infinite, anything less than infinite is still infinite. That's what infinity means. The shown algorithm is logically flawed, and clearly results in infinite recursion. Let's label some of these recursive calls as follows:

if (this->check(maze, path, x + 1, y, z) ||   // A
    this->check(maze, path, x, y + 1, z) ||   // B
    this->check(maze, path, x, y, z + 1))     // C
{
    checking++;
}

if (this->check(maze, path, x - 1, y, z) && checking == 1) // D
{
    checking++;
}

The initial value of checking is 0. We can draw the following conclusions based on the above code.

1) Recursive call A always takes place.

2) there's some set of coordinates for which either A, or B, or C recursive cals returns true

3) And when condition 2) holds true, recursive call D always takes place.

Therefore, whenever condition "2)" is true, this guarantees infinite recursion. Recursive call A which then makes recursive call D is logically infinite recursion.

This is because prior to the recursive call that results in condition 2) being true, recursive call A passes x+1. And inside the recursive call condition "2)" evaluates to true, which results in recursive call D.

But this results in two consecutive nested recursive calls, first passing x+1, then x+1-1 on the second one, with the same y and z values. The second recursive call then passes the same values for x, y, and z as its grandparent call, and there's nothing here that will stop this infinite recursion.

The shown algorithm is fundamentally broken. You will need to figure out why it's broken, and what should be the correct algorithm. This cannot be answered based on the limited information in the question, the only thing that can be trivially determined is the reason, and the explanation why infinite recursion occurs; it's rather obvious.

Collectives™ on Stack Overflow

Function with recursion is causing stack overflow

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