c++ - 递归函数导致堆栈溢出

Question

我的函数在 1 和 0 的迷宫中寻找路径时遇到问题，如果它在该路径上或已找到导出，则返回 true，如果迷宫无法解决，则返回 false。每当我尝试检查我的变量的“-1s”时，我都会收到堆栈溢出错误，但我的基本情况应该可以防止这种情况发生。有没有办法通过递归使用更少的堆栈空间？这是我的代码

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

Answer 1

你不能使用“更少的堆栈空间”，原因很简单，当所需的堆栈空间量是无限时，任何小于无限的东西仍然是无限的。这就是无限的意思。所示算法在逻辑上有缺陷，显然会导致无限递归。让我们将其中一些递归调用标记如下:

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

checking的初始值为0，根据上面的代码我们可以得出以下结论。

1) 递归调用 A 总是发生。

2) 有一些坐标集，A、B 或 C 递归计算返回 true

3) 当条件 2) 成立时，递归调用 D 总是发生。

因此，只要条件“2)”为真，就可以保证无限递归。递归调用 A 然后递归调用 D 在逻辑上是无限递归。

这是因为在导致条件 2) 为真的递归调用之前，递归调用 A 传递了 x+1。在递归调用条件“2)”中计算结果为真，这导致递归调用 D。

但这会导致两次连续的嵌套递归调用，首先传递 x+1，然后在第二个传递 x+1-1，具有相同的 y 和 z 值。然后，第二个递归调用将相同的值传递给 x、y 和 z 作为其祖父调用，这里没有任何东西可以阻止它无限递归。

所示算法从根本上被破坏了。您将需要弄清楚它为什么坏了，以及正确的算法应该是什么。这不能根据问题中有限的信息来回答，唯一可以简单确定的是原因，以及为什么会发生无限递归的解释；这很明显。