函数与递归导致堆栈溢出

我有一个问题，我的功能在1s和0s迷宫中找到路径，返回true，如果它是在该路径上或已找到退出，并返回false如果迷宫是无法解决的。每当我尝试检查我的变量的“-1”时，发现堆栈溢出错误，但是我的基本案例应该阻止这种情况发生。有没有办法使用递归更少的堆栈空间？这里是我的代码函数与递归导致堆栈溢出

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

来源

2017-10-20 Taylor Southwick

这听起来像你的功能永远不会停止递归。您是否考虑过使用调试器来追踪代码或添加一些日志记录，以便了解实际发生的情况？ –

这不是问题，但前五个if语句的括号太多了。你不需要任何内在的东西。 –

*有没有办法使用递归较少的堆栈空间？* - 到目前为止，您还没有证明问题是堆栈空间。如果它只是你的代码中的一个错误，或者你的逻辑错误导致堆栈溢出，而不仅仅是你是一个迷宫？另外，你测试了哪些数据？如果您还没有这样做，我建议您使用更小的迷宫，以确保这不仅仅是一个错误。 – PaulMcKenzie

不能使用“较少的堆栈空间”，原因很简单，当所需的堆栈空间的数量是无限的，任何低于无限仍然是无穷的。这就是无限的意义。所示的算法在逻辑上是有缺陷的，并且清楚地导致无限递归。让我们来标注一些递归调用如下：

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递归CALS回报true

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

因此，只要条件“2）”为真，这就保证了无限递归。递归调用A然后进行递归调用D是逻辑无限递归。

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

但是这会导致连续两个嵌套的递归调用，首先经过x+1，然后x+1-1上第二个，与同y和z值。第二次递归调用然后将x,y和z的值作为其祖父的调用传递，并且这里没有任何东西可以阻止这种无限递归。

显示的算法基本上被破坏。你需要弄清楚它为什么会坏掉，以及什么应该是正确的算法。根据问题中的有限信息无法回答这个问题，唯一可以轻易确定的是理由，并解释为什么发生无限递归;这很明显。

来源

2017-10-20 02:30:09

函数与递归导致堆栈溢出

回答

相关问题