使用遞歸進行3D數組操作 - 導致StackOverflow（不是無限！）

Question

我最近昨天發佈了一個關於類似問題的問題，但我編寫了一些有點不同的東西，現在有一個不同的問題。這是我的代碼導致StackOverflow。

**請注意，3D網格陣列超過100萬個元素，可以達到約6400萬個元素（存儲枚舉）。

**另外請注意，這不會進入無限。在小數據集上，這個算法工作正常。

這可能是由極端遞歸引起的嗎？我如何處理這個（這是我的算法的重要部分！）？我已經做了一些研究，並聽到使用隊列，甚至只是大量的for循環。

什麼會降低引起堆棧溢出的可能性？

謝謝！

/** 
* Fills all void cells in the 3D grid of Atom. 
* 
* @param x 
*   The starting x coordinate 
* @param y 
*   The starting y coordinate 
* @param z 
*   The starting z coordinate 
*/ 
private void fillAllVoidCells(int x, int y, int z) 
{ 
    // Base case -- If not BLOATED_ATOM, BOUNDING_BOX, 
    // or VOID then must be a cavity (only 4 CellType 
    // enum types. 
    if ((grid[x][y][z] == CellType.BLOATED_ATOM) 
     || grid[x][y][z] == CellType.BOUNDING_BOX 
     || grid[x][y][z] == CellType.VOID) 
    { 
     // Pop off runtime stack 
     return; 
    } 
    else 
    { 
     // Set to void then check all surrounding cells. 
     grid[x][y][z] = CellType.VOID; 

     fillAllVoidCells(x + 1, y, z); // right 
     fillAllVoidCells(x - 1, y, z); // left 
     fillAllVoidCells(x, y + 1, z); // in front 
     fillAllVoidCells(x, y - 1, z); // behind 
     fillAllVoidCells(x, y, z + 1); // above 
     fillAllVoidCells(x, y, z - 1); // below 
    } 
} 

=====編輯======新的方法來實現使用堆棧（每Roee Gavirel幫助） 這將是一個正確實施？

// ---------------------------------------------------------- 
    /** 
    * Fills all void cells in the 3D grid of Atom. 
    * 
    * @param x 
    *   The starting x coordinate 
    * @param y 
    *   The starting y coordinate 
    * @param z 
    *   The starting z coordinate 
    */ 
    private void fillAllVoidCells(int x, int y, int z) 
    { 
     Point p = new Point(x, y, z); 

     stack.push(p); 

     while (!stack.isEmpty()) 
      p = stack.top(); 
     stack.pop(); 

     // Base case -- If not BLOATED_ATOM, BOUNDING_BOX, 
     // or VOID then must be a cavity (only 4 CellType 
     // enum types. 
     CellType state = grid[p.x][p.y][p.z]; 

     if ((state == CellType.BLOATED_ATOM) || state == CellType.BOUNDING_BOX 
      || state == CellType.VOID) 
     { 
      return; 
     } 
     else 
     { 
      // Set to void then check all surrounding cells. 
      grid[p.x][p.y][p.z] = CellType.VOID; 
      Point tempP = p; 

      tempP.x = p.x - 1; 
      stack.push(tempP); 
      tempP.x = p.x + 1; 
      stack.push(tempP); 
      tempP.x = p.x; // return to original x coordinate 

      tempP.y = p.y - 1; 
      stack.push(tempP); 
      tempP.y = p.y + 1; 
      stack.push(tempP); 
      tempP.y = p.y; // return to original y coordiante 

      tempP.z = p.z - 1; 
      stack.push(tempP); 
      tempP.z = p.z + 1; 
      stack.push(tempP); 
      tempP.z = p.z; // return to original z coordinate 
     } 
    } 

Answer 1

這很可能會導致溢出。你可以（也應該）做的是避免使用你自己的棧來處理數據並避免遞歸。

在你的情況下：
1.有一堆相關點（x，y，z），它們的起始點與fillAllVoidCells相同。
2. while堆棧不爲空應該執行檢查
3.如果是cavity將周圍點添加到堆棧。

== ==編輯 類似的東西：

struct point { 
    int x,y,z; 
} 

private void fillAllVoidCells(int x, int y, int z) 
{ 
    std::list<point> Ps; 
    point p; 
    p.x = x; 
    p.y = y; 
    p.z = z; 
    Ps.push_back(p); 

    while (!Ps.empty()) 
     p = Ps.back(); 
     Ps.pop_back(); 

     // Base case -- If not BLOATED_ATOM, BOUNDING_BOX, 
     // or VOID then must be a cavity (only 4 CellType 
     // enum types. 
     auto state = grid[p.x][p.y][p.z]; 
     if ((state == CellType.BLOATED_ATOM) 
      || state == CellType.BOUNDING_BOX 
      || state == CellType.VOID) 
     { 
      continue; 
     } 
     else 
     { 
      // Set to void then check all surrounding cells. 
      grid[p.x][p.y][p.z] = CellType.VOID; 

      point tempP = p; 
      tempP.x = P.x - 1;  
      Ps.push_back(tempP); 
      tempP.x = P.x + 1;  
      Ps.push_back(tempP); 
      tempP.y = P.y - 1;  
      Ps.push_back(tempP); 
      tempP.y = P.y + 1;  
      Ps.push_back(tempP); 
      tempP.z = P.z - 1;  
      Ps.push_back(tempP); 
      tempP.z = P.z + 1;  
      Ps.push_back(tempP); 
     } 
    } 
}