Javaで島の数を数えるプログラムを作成した際に「java.lang.StackOverflowError」が発生してしまう

Question

前提・実現したいこと

マス目状の盤上にある「島の数」を数えるプログラムを作成しています。
イメージは「https://www.techiedelight.com/count-the-number-of-islands/」のような感じです。このサイトでは斜めも同一の島としていますが、今回は上下左右のみを同一島と見なそうとしています）

再帰処理を行って正解を導き出す所までは出来たのですが、入力のデータが大規模になると「java.lang.StackOverflowError」が発生してしまいます。

調べた所「末尾再帰」の解決策に辿り着いたのですが、ほぼ全てint型のメソッドのreturn値を修正する内容が記載されており、void型の場合の解決策が分かりませんでした。
次のようなJavaのプログラムで「java.lang.StackOverflowError」が発生した場合、コードの中でハンドリングする際の記述方法についてご教授をお願いしたいです。

発生している問題・エラーメッセージ

Exception in thread "main" java.lang.StackOverflowError

該当のソースコード

package test;
public class NumberOfIslands {
    public static void main(String[] args) {

        int colnum = 99;
        int rownum = 100;
        String row[] = new String[rownum];

        for(int i=0; i<rownum; i++) {
                row[i]="1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1";
        }

        int island[][] = new int[rownum][colnum];
        int shima_count =0;

        for(int i=0; i<rownum; i++){
            for(int j=0; j<colnum; j++){
                island[i][j] = Integer.parseInt(row[i].substring(2*j,2*j+1));
            }
        }

        for(int i=0; i<rownum; i++){
            for(int j=0; j<colnum; j++){
                if(island[i][j]==1){
                    shima_count++;
                    dxySearch(i,j,rownum,colnum,island);
                }
            }
        }

        System.out.println(shima_count);
    }

    public static void dxySearch(int is, int js, int rownum_s, int colnum_s, int[][] island_s){
        if(is<0 || is>=rownum_s || js<0 || js>=colnum_s){
            return;
        }
        if(island_s[is][js]!=1){
            return;
        }
        island_s[is][js] = 0;
        dxySearch(is+1,js,rownum_s,colnum_s,island_s);
        dxySearch(is-1,js,rownum_s,colnum_s,island_s);
        dxySearch(is,js+1,rownum_s,colnum_s,island_s);
        dxySearch(is,js-1,rownum_s,colnum_s,island_s);
    }
}

試したこと

「末尾再帰」について調べていたのですが、int型のメソッドのreturn値を修正する内容が記載されているものが多く、void型の場合の解決策が分かりませんでした。

補足情報（FW/ツールのバージョンなど）

OS : CentOS release 6.9 (Final)
Eclipse：Eclipse(OXYGEN)
Tomcat : v8.5

ここにより詳細な情報を記載してください。

Answer 1

根本的に各ステップで4種類の再帰を呼び出さなければならないため、「末尾再帰」は不可能だと思われます。そもそもスタックオーバーフローの原因解消にならないと思いますし。

たどる場所情報がわかればいいので、その情報だけスタックに積むなどしてループすればいいと思います。

    public static void dxySearch(int is, int js, int rownum_s, int colnum_s, int[][] island_s){
        // スタックに積むための位置情報を詰めるクラス
        // どうせここでしか使わないだろうとローカルクラスにしましたが、
        // 必要に応じて外に出してください
        class Point {
            final int i, j;
            Point(int is, int js) {
                i = is; j = js;
            }
        }

        Deque<Point> pointStack = new ArrayDeque<>();
        pointStack.addFirst(new Point(is, js);
        Point p;
        while ((p = pointStack.pollFirst()) != null) {
            if(p.i<0 || p.i>=rownum_s || p.j<0 || p.j>=colnum_s){
                continue;
            }
            if(island_s[p.i][p.j]!=1){
                continue;
            }
            island_s[p.i][p.j] = 0;
            pointStack.addFirst(new Point(p.i+1, p.j);
            pointStack.addFirst(new Point(p.i-1, p.j);
            pointStack.addFirst(new Point(p.i, p.j+1);
            pointStack.addFirst(new Point(p.i, p.j-1);
        }
    }

Comments

[MeguroHarumi]

ご回答頂きありがとうございます、具体的なコードも提示頂き大変参考になります。理解が追い付いておらず恐縮ですが、「4種類の再帰を～」→「末尾再帰が不可能」となる理由がよく分かりませんでした。また、末尾再帰がスタックオーバーフローの原因解消にならない理由についても分からず・・お手数ですがご教示頂けないでしょうか？

あと下記行について意図を理解できた自信がなかったので、念のため確認ですが「!」の前に「)」が必要でしょうか？
(whileの条件はスタックから抜いた最新の値でpを更新し、かつそれがnullでない？？)
while ((p = pointStack.pollFirst() != null) {
↓
while ((p = pointStack.pollFirst()) != null) {

[swordone]

)の不足指摘ありがとうございます。その通りです。修正しました。

質問に対してですが、そもそも｢末尾再帰｣は、再帰の中でも再帰の呼び出しをメソッドの最後にしているものを指します。4種類の再帰呼び出しがある以上、すべてを最後にはできない(最後に4種類呼び出しても、｢最後の1つ前の行｣などが必ず存在する)ので、そう言いました。

また末尾再帰も結局｢再帰｣なので、しすぎるとスタックオーバーフローになります。

そもそも末尾再帰とか言う話は、｢末尾再帰の最適化｣などの話ではないでしょうか？

[MeguroHarumi]

ご教示頂きありがとうございます、大変分かりやすいです。また頂いたコードを組み込んで、スタックオーバーフローなく動作する事を確認できました。

Answer 2

[0][0]から添字が増える方向に順に探すのでしたら, 減る方向は検索する必要がありません.
次のように2方向のみにしては如何でしょうか.

  dxySearch(is+1,js,rownum_s,colnum_s,island_s);
  //dxySearch(is-1,js,rownum_s,colnum_s,island_s);
  dxySearch(is,js+1,rownum_s,colnum_s,island_s);
  //dxySearch(is,js-1,rownum_s,colnum_s,island_s);

すいません, これでは島を正確にカウント出来なさそうです.

Comments

[MeguroHarumi]

ご回答頂きありがとうございます。実は私もその考えを一度試してみたのですが、以下のケースのisland[4][1]のようなマスが新規の島とカウントされるため、左&上の検索も必要と気づきました。

0 1 1 0
1 0 1 0
1 0 0 0
0 0 1 1
0 1 1 1

[jimbe]

根本的なことですが, 再帰じゃないといけないのでしょうか.
再帰でのやり方を考えるよりも, キューとループに書き換えたほうが完成は早い気がします.

[MeguroHarumi]

ご回答頂きありがとうございます。理解が追い付いておらず恐縮ですが、再帰よりもキューとループの方が～という判断に至った理由を教えて頂けないでしょうか？

[jimbe]

再帰では, 呼び出した(=島と判断した)回数分のスタックは終わるまで解放されません.
キュー(とループ)では, 島と判断したキューのデータは即削除出来ますので, キューは再帰のスタック程には溜まらないのではないかと思われるためです.

[MeguroHarumi]

ご教示頂きありがとうございます、理解できました！引き出しを増やすためにもトライしてみようと思います。

Answer 3

island_s[][] の各要素は何の時に何を意味しているか、確認してください。

そこがうまく処理できていないので再帰処理が爆発しているような……

Comments

[MeguroHarumi]

ご回答頂きありがとうございます。

[tacsheaven]

多分ワーストケースですが、とぐろを巻くように（というか蚊取り線香？）すると、サイズが (x,y) のとき
x + (y-1) + (x-1) + (y-2) +
(x-2) + (y-3) + (x-3) + (y-4) + ...
と、凄まじい数のスタック消費することになるような。

[MeguroHarumi]

ご回答頂きありがとうございます。