递归时如何处理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数据结构是堆的一部分。