再帰時にStackOverflowエラーを処理するには？

Question

私は現在、サイズがのnマップを読み込んでいます。 * nです。この「地図」は、.および*の文字で構成され、.は水を表し、*は土地を表します。プログラムのポイントは、マップ上に何個の「島」が存在するかを数えることです。ここで、「島」は水で完全に囲まれた土地（*）です（.）。伝統的な8方向のいずれかに2つの土地（*）が接続されている場合、それらは1つの島とみなされます。参考までに、最後に入力と出力のサンプルを入れます。私も含まれます

私のコードは、それが*に遭遇するたびint numOfIslandsをインクリメント、マップと一致した2D char配列を解析します。次に、*を.に置き換え、再帰を使用して、その「島」の残りの部分を見つけて置き換え、トラバーサルで移動します。現在のところ、サンプルの入力など、より小さな入力サイズで動作します。しかし、問題は入力サイズが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

あなたのアルゴリズムをあまり詳しく勉強することなく、私は疑いがある同じ細胞を2回以上チェックしているため、検索の深さが指数関数的に増加します。これを回避するための鈍いしかし効果的な方法は、すでにテストされたセルのキャッシュを保持し、見つかった場合にキャッシュされた結果を使用することです。いくつかのプラットフォームでは、あなたが本当に深いスタックが必要なのかがあれば

---

...

、あなたはより多くのスタックに自分でアクセスしてスレッドを取得するために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データ構造がヒープの一部であることを除いて、 "To-doリスト"としてLIFOスタックを使用するのと同じ原理を使用します。