再帰メソッドについて

質問

いつもお世話になっております。
再帰メソッドについて質問があります。

後述のプログラム実行後、以下の結果が
得られました。

********** depth = [0] , value = [0]
********** depth = [1] , value = [1]
********** depth = [2] , value = [2]
########## depth = [2] , value = [3] …★
########## depth = [1] , value = [3]

recursionMethod() は3回呼ばれました。

（以下、ソース）
public class RecursionTest {

private static final int MAX_DEPTH = 2;
private static int cnt = 0;
private int val =0;

public static void main(String[] args) {
// 再帰メソッドの呼び出し
RecursionTest own = new RecursionTest();
own.recursionMethod(0);
System.out.println("\n recursionMethod() は" + cnt + "回呼ばれました。");
}

private void recursionMethod(int depth) {
// 再帰メソッドが呼ばれた回数をカウントする
cnt++;
System.out.println("********** depth = [" + depth + "] , value = [" + val + "]");
val++;

// パラメータ depth が MAX値に到達したら、return する
if (depth++ >= MAX_DEPTH) {
return;
}

// 自分自身の呼び出し
recursionMethod(depth);
System.out.println("########## depth = [" + depth + "] , value = [" + val + "]");
}
}

実行結果の★以降が得られる理由が全く分かりません。

・return で main() に戻るはずなのになぜ「###～」のログが出力されるのか
・depth の値がなぜデクリメントされるのか
（誰がデクリメントの処理をしているのか）

そもそも上記の結果を返すことが「メソッドの再帰的呼び出し」ということなのでしょうか？

ご教授頂ける方がいらっしゃいましたら、宜しくお願い致します。

回答No.4

run34ricky · ベストアンサー

daisy_kさん、こんにちは

betagamma さんが回答された通り、returnするからと言って、mainメソッドに戻るわけではありません。そのメソッドを呼び出したメソッドに戻るだけです。
またデクリメント処理についてですが、結論から言うと行われているわけではありません。
Javaを含め、メソッドの再起呼び出しをサポートしている言語では、メソッドが自身を呼んでも、あくまでメソッドロジックの再利用をしているだけで、メソッドの中で宣言しているローカル変数は再利用していないのです。ローカル変数は、そのメソッドを呼び出すたびに、別の領域に生成し直され、呼び出し元と呼び出し先では名前が一致しても別物の変数として扱われます。
そして引数である depth も、メソッド内だけで有効なローカル変数なのです。
１回目のrecursionMethodメソッド内のdepth（※１）は０で始まり１になりました。
その後、recursionMethodメソッドを呼び出しています。その引数であるdepth（※２）は、※１のdepthと別に生成されて、※２のdepthの値をいくら変更しようと※１のdepthは一切影響を受けません。
流れを図示すると以下の通りになると思います。

mainメソッド
┌
│→呼出
│　recursionMethodメソッド
│　┌
│　│このメソッド内のdepthは、０で初期化
│　│*とdepth(０)を出力
│　│depth++
│　│このメソッド内のdepthは、１に変化。
│　│→呼出
│　│　recursionMethodメソッド
│　│　┌
│　│　│このメソッド内のdepthは、１で初期化
│　│　│*とdepth(１)を出力
│　│　│depth++
│　│　│このメソッド内のdepthは、２に変化。
│　│　│→呼出
│　│　│　recursionMethodメソッド
│　│　│　┌
│　│　│　│このメソッド内のdepthは、２で初期化
│　│　│　│*とdepth(２)を出力
│　│　│　│depth++
│　│　│　│このメソッド内のdepthは、３に変化。
│　│　│　│return
│　│　│　└
│　│　│←戻り
│　│　｜このメソッド内のdepthは、２のまま
│　│　│#とdepth(２)を出力
│　│　└
│　│←戻り
│　｜このメソッド内のdepthは、１のまま
│　│#とdepth(１)を出力
│　└
│←戻り
└

お礼

run34rickyさん、ご回答ありがとうございます。

非常に分かりやすいご説明で、フローがしっかり
理解できました。

大変勉強になりました。
ありがとうございました。

回答No.5

betagamma

No.1です。run34rickyさんの図を見ればわかるのではないでしょうか？

実は,自分もこのように、字下げして書いたのですが,投稿したら字下げが消されてしまって・・・字下げが消されたら意味不明ですよね.申し訳ありません。

回答No.3

ngsvx

再帰呼び出しは、ややこしくなることがよくありますね。

とりあえず、入り口（１箇所）と出口（２箇所）で表示したらどうですか？

その時に、どの深度なのかを表示したところですが、
このソースでは引数depthを直接操作しているので、
入り口の直後で

int curDepth = depth;

などとして、入り口と出口でcurDepthを表示したらどうでしょうか。

お礼

ご回答ありがとうございました。

回答No.2

torakiyojp

こんにちは。

> だとしたら、なぜ depth がデクリメントされるのですか？

デクリメントされているわけではありません。
元々の呼び出し元に戻っているだけです。

main
→recursionMethod(A) depth=0→depth++→depth=1
→recursionMethod(B) depth=1→depth++→depth=2
→recursionMethod(C) depth=2
→recursionMethod(B) depth=2
→recursionMethod(A) depth=1
→main

お礼

ご回答ありがとうございました。

処理の流れを理解する参考になりました。

回答No.1

betagamma

まず、returnで直接mainに戻るわけではありません。return戻るのは,呼び出し先の関数です。ここがおそらく理解していないポイントなのではないかと思います.
このrecursionMethod（recursiveMethodの方が英語としては正しいですが）は、
A:***depthを表示する
B:val++;if(depth++>=MAX_DEPTH)return;
C:recursionMethod(depth)
D:####depthを表示する
の四箇所から構成されています。
A:depth=0
B:depth=1,val=1
C:depth=1でrecursionMethodを呼び出す。
A:depth=1なので二行目を表示(val=2)
B:depth=2,val=2
C:depth=2でrecursionMethodを呼び出す.
A:depth=2なので三行目を表示(val=2)
B:val=3にしてから、returnで戻る
D:☆depth=2,val=3で、四行目を表示。
D:depth=1,val=3で、５行目を表示

わかりましたでしょうか？ここで、気をつけていただきたいのは、depthとvalの根本的な違いです。☆のところがおそらくわかっていらっしゃらないのだと思うのですが、
void func(int depth){
depth++;
A(depth);
System.out.println(depth);
}
という関数があったとしたら、Aがどのような関数であったとしても、受け取ったdepth+1の値がそのまま表示されるはずですよね？今は、このAがrecursionMethodになっているだけです。

一方、valは引数ではないので、実体は一つです。

補足

betagammaさん、早速のご回答ありがとうございます。
いくつか確認させて頂きたいのですが、
よろしくお願い致します。

> A:depth=1なので二行目を表示(val=2)
この部分では まだ val=1 だと思うのですが、どうでしょうか？

> B:val=3にしてから、returnで戻る
ここの returnで戻る戻り先は、recursionMethod(depth);
ということなのですね。
recursionMethod(0); の呼び元である main()に返るのだと思っていました。

そうすると、4行目が出力されるのは納得できました。

しかし、最後の 1行(5行目)が出力されるのが
やはり分かりません。

4行目を実行した時点で、recursionMethod(depth) の処理は
終了し、main()に返るような気がするのですが…

eclipse のデバッグモードで 1行1行
実行していくと、4行目を出力後、カーソルは

} // recursionMethod() の終了括弧

に移動して再び
System.out.println("###～
を実行し、5行目を出力後 main()に返ります。

これも戻り先が main()ではなく、
recursionMethod(depth) だからということなのですよね？
だとしたら、なぜ depth がデクリメントされるのですか？

長々とまとまりのない説明で申し訳ありませんが、
よろしかったら補足説明を頂けますでしょうか。