質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

Q&A

解決済

3回答

1978閲覧

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

MeguroHarumi

総合スコア14

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

0グッド

0クリップ

投稿2019/08/26 07:46

前提・実現したいこと

マス目状の盤上にある「島の数」を数えるプログラムを作成しています。
イメージは「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

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

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答3

0

ベストアンサー

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

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

java

1 public static void dxySearch(int is, int js, int rownum_s, int colnum_s, int[][] island_s){ 2 // スタックに積むための位置情報を詰めるクラス 3 // どうせここでしか使わないだろうとローカルクラスにしましたが、 4 // 必要に応じて外に出してください 5 class Point { 6 final int i, j; 7 Point(int is, int js) { 8 i = is; j = js; 9 } 10 } 11 12 Deque<Point> pointStack = new ArrayDeque<>(); 13 pointStack.addFirst(new Point(is, js); 14 Point p; 15 while ((p = pointStack.pollFirst()) != null) { 16 if(p.i<0 || p.i>=rownum_s || p.j<0 || p.j>=colnum_s){ 17 continue; 18 } 19 if(island_s[p.i][p.j]!=1){ 20 continue; 21 } 22 island_s[p.i][p.j] = 0; 23 pointStack.addFirst(new Point(p.i+1, p.j); 24 pointStack.addFirst(new Point(p.i-1, p.j); 25 pointStack.addFirst(new Point(p.i, p.j+1); 26 pointStack.addFirst(new Point(p.i, p.j-1); 27 } 28 }

投稿2019/08/26 15:44

編集2019/08/30 12:54
swordone

総合スコア20649

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

MeguroHarumi

2019/08/30 11:49

ご回答頂きありがとうございます、具体的なコードも提示頂き大変参考になります。理解が追い付いておらず恐縮ですが、「4種類の再帰を~」→「末尾再帰が不可能」となる理由がよく分かりませんでした。また、末尾再帰がスタックオーバーフローの原因解消にならない理由についても分からず・・お手数ですがご教示頂けないでしょうか? あと下記行について意図を理解できた自信がなかったので、念のため確認ですが「!」の前に「)」が必要でしょうか? (whileの条件はスタックから抜いた最新の値でpを更新し、かつそれがnullでない??) while ((p = pointStack.pollFirst() != null) { ↓ while ((p = pointStack.pollFirst()) != null) {
swordone

2019/08/30 13:02

)の不足指摘ありがとうございます。その通りです。修正しました。 質問に対してですが、そもそも「末尾再帰」は、再帰の中でも再帰の呼び出しをメソッドの最後にしているものを指します。4種類の再帰呼び出しがある以上、すべてを最後にはできない(最後に4種類呼び出しても、「最後の1つ前の行」などが必ず存在する)ので、そう言いました。 また末尾再帰も結局「再帰」なので、しすぎるとスタックオーバーフローになります。 そもそも末尾再帰とか言う話は、「末尾再帰の最適化」などの話ではないでしょうか?
MeguroHarumi

2019/09/02 23:16

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

0

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

java

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

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

投稿2019/08/26 08:52

編集2019/08/26 09:24
jimbe

総合スコア12545

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

MeguroHarumi

2019/08/26 09:31

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

2019/08/26 12:48

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

2019/08/30 11:52

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

2019/08/30 12:16

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

2019/09/02 23:15

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

0

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

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

投稿2019/08/26 08:23

編集2019/08/26 08:24
tacsheaven

総合スコア13703

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

MeguroHarumi

2019/08/26 09:36

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

2019/08/27 06:54

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

2019/08/30 11:52

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問