遞歸時如何處理StackOverflow錯誤？

Question

我目前正在制定一項計劃，在讀取尺寸ň * ñ的「地圖」。這個「地圖」是由字符.和*，其中.代表水，並*代表土地。該方案的一點是要計算有多少「島」發生在地圖，其中一個「島」是土地（*）任何部件（或多個）上，完全由水（.）包圍。如果兩個地塊（*）在傳統的八個方向中的任何一個相連，則它們被認爲是一個島。作爲參考，我將在末尾放置一個示例輸入和輸出。

我的代碼還包括解析匹配地圖的2D char數組，每遇到*就增加int numOfIslands。然後，它取代了*與.，並使用遞歸來查找和替換「孤島」的其餘部分，與穿越移動之前。它目前適用於較小的輸入大小，例如包含的示例輸入。但問題是，它需要能夠對n = 1000輸入尺寸運行，目前我得到的StackOverflow錯誤，當我嘗試在輸入尺寸大的運行它。我應該怎麼做來處理StackOverflow錯誤？我想這與在遞歸過程中破壞有關，爲了「卸載」堆棧，但是我真的不知道如何開始這樣做，而且我的網絡研究一直沒有成果。

我遍歷和遞歸代碼，其中map[][]是2D char陣列輸入的文件相匹配：

//traverses the map, looking for 1s, and then sets that location to 0 before running testLocation on it 
public static void traverse() { 
    for (int col = 0; col < n; col++) { 
     for (int row = 0; row < n; row++) { 
      if (map[row][col] == '*') { 
       map[row][col] = '.'; 
       testLocation(row, col); 
       numOfIslands++; 
      } 
     } 
    } 
}  

//takes in a land location, and makes that land, along with the rest of the "island" 0s 
public static void testLocation(int row, int col) { 
    //test upper left 
    if (row > 0 && col > 0) { 
     if (map[row - 1][col - 1] == '*') { 
      map[row - 1][col - 1] = '.'; 
      testLocation(row - 1, col - 1); 
     } 
    } 

    //test upper 
    if (row > 0) { 
     if (map[row - 1][col] == '*') { 
      map[row - 1][col] = '.'; 
      testLocation(row - 1, col); 
     } 
    } 

    //test upper right 
    if (row > 0 && col < n - 1) { 
     if (map[row - 1][col + 1] == '*') { 
      map[row - 1][col + 1] = '.'; 
      testLocation(row - 1, col + 1); 
     } 
    } 

    //test left 
    if (col > 0) { 
     if (map[row][col - 1] == '*') { 
      map[row][col - 1] = '.'; 
      testLocation(row, col - 1); 
     } 
    } 

    //test right 
    if (col < n - 1) { 
     if (map[row][col + 1] == '*') { 
      map[row][col + 1] = '.'; 
      testLocation(row, col + 1); 
     } 
    } 

    //test lower left 
    if (row < n - 1 && col > 0) { 
     if (map[row + 1][col - 1] == '*') { 
      map[row + 1][col - 1] = '.'; 
      testLocation(row + 1, col - 1); 
     } 
    } 

    //test lower 
    if (row < n - 1) { 
     if (map[row + 1][col] == '*') { 
      map[row + 1][col] = '.'; 
      testLocation(row + 1, col); 
     } 
    } 

    //test lower right 
    if (row < n - 1 && col < n - 1) { 
     if (map[row + 1][col + 1] == '*') { 
      map[row + 1][col + 1] = '.'; 
      testLocation(row + 1, col + 1); 
     } 
    } 
} 

樣品輸入：

...*. 
**..* 
*.... 
*.*.* 
**... 

示例輸出：

The total number of islands is 3 

Answer 1

沒有太多細節的研究你的算法，我有一個懷疑您不止一次檢查同一個單元格，導致搜索深度呈指數級增長。避免這種情況的一種直接但有效的方式是保留已經測試過的單元的緩存，並在找到的地方使用緩存結果。

---

但是，如果你真的需要深堆棧...

在某些平臺上，你可以使用public Thread(ThreadGroup group, Runnable target, String name, long stackSize)讓自己訪問一個線程更多的堆棧。

但Javadoc警告：「在某些平臺上，stackSize參數的值可能不起任何作用。」

---

如果算法肯定需要一個堆棧，但JRE的調用堆棧是太小了，你可以把它翻譯成一個使用它自己的堆棧中的堆內存版本。

void move(int num, int from, int to, int using) { 
    if(num == 1) { 
     println("%d to %d\n", from, to); 
    } else { 
     move(num-1, from, using, to); 
     move(1, from, to, using); 
     move(num-1, using, to, from); 
    } 
} 

你可以做等同：

Stack<Task> stack = new Stack<>(); 
stack.push(new Task(num, from, to, using)); 
while(!s.empty()) { 
    doTask(stack); 
} 

void doTask(Stack<Task> stack) { 
    Task t = stack.pop(); 

    if t.num == 1 { 
     printf("%d to %d\n", from, to); 
    } else { 
     stack.push(new Task(t.num-1, t.using, t.to, t.from)); 
     stack.push(new Task(1, t.from, t.to, t.using)); 
     stack.push(new Task(t.num-1, t.from, t.using, t.to)); 
    } 
} 

這不是遞歸的，所以它不會創建一個深呼

例如使用河內的老經典塔遞歸這裏的疊加。但它仍然使用與LIFO堆棧相同的原理作爲「待辦事項列表」，除了現在LIFO數據結構是堆的一部分。