函數與遞歸導致堆棧溢出

我有一個問題，我的功能在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

函數與遞歸導致堆棧溢出

回答

相關問題