【Java】再帰的なプログラムで予期せぬ動作をする

質問

【環境】
java version "1.6.0_31"
Java(TM) SE Runtime Environment (build 1.6.0_31-b05)
Java HotSpot(TM) 64-Bit Server VM (build 20.6-b01, mixed mode)
----------------------------------------------------------------
以下のようなプログラムを書いたのですが、自分が予測していた動作と異なり、困っています。
私は

-------------Start-------------
カウント----------->0
2で割り切れちゃった----------->0
カウント----------->1
2で割り切れなかった----------->1
カウント----------->2
2で割り切れちゃった----------->2
カウント----------->3
2で割り切れなかった----------->3
カウント----------->4
2で割り切れちゃった----------->4
-------------End-------------

という動作を期待していたのですが、実際は

-------------Start-------------
カウント----------->0
2で割り切れちゃった----------->0
カウント----------->1
2で割り切れなかった----------->1
カウント----------->2
2で割り切れちゃった----------->2
カウント----------->3
2で割り切れなかった----------->3
カウント----------->4
2で割り切れちゃった----------->4
2で割り切れなかった----------->5
2で割り切れなかった----------->6
2で割り切れなかった----------->7
-------------End-------------

となってしまいました。考えても、どうしてこのように動作するのか理解できなかったので、こちらに質問しました。よろしくお願いします(ソースコードは下です)。

-----------------以下、ソースコード-----------------
Main.java

public class Main
{
　　　　public static void main(String args[])
　　　　{
　　　　　　　　Saiki saiki = new Saiki();
　　　　　　　　System.out.println("-------------Start-------------");
　　　　　　　　saiki.playSaiki();
　　　　　　　　System.out.println("-------------End---------------");
　　　　}
}

Saiki.java

public class Saiki
{
　　private int counter;
　　Saiki()
　　{
　　　　counter = 0;
　　}
　　public void playSaiki()
　　{
　　　　if(counter < 5)
　　　　{
　　　　　　System.out.println("カウント----------->" + counter);
　　　　　　if(counter%2 == 0)
　　　　　　{
　　　　　　　　System.out.println("2で割り切れちゃった----------->" + counter);
　　　　　　　　counter++;
　　　　　　　　playSaiki();
　　　　　　}
　　　　　　System.out.println("2で割り切れなかった----------->" + counter);
　　　　　　counter++;
　　　　　　playSaiki();
　　　　}
　　}
}

回答No.2

root139 · ベストアンサー

既に回答が付いていますが、2で割り切れる場合もifブロックの中での再起処理が終わった後にその下の処理が続けて行われるからですね。

下記の様にいくつか簡単な修正方法がありますが、修正後のソースから考えた方が分かりやすいかもしれません。

a. 2で割り切れる場合のifブロックの最後でメソッドを抜ける

例) ------------------------------------
if (counter %2 == 0)
{
　　System.out.println("2で割り切れちゃった----------->" + counter);
　　counter++;
　　playSaiki();
　　return; // この行を追加
}
----------------------------------------

b. ifで場合分けするのは、メッセージの表示部分だけにする

例) ------------------------------------
if (counter %2 == 0)
{
　　System.out.println("2で割り切れちゃった----------->" + counter);
}
else
{
　　System.out.println("2で割り切れなかった----------->" + counter);
}

counter++;
playSaiki();
----------------------------------------

お礼

回答ありがとうございます。
疑問に答えるだけでなく、改善策まで書いてくれるなんて...ほんとに感謝です。
修正するなら、2つ目のコードの方が無駄が少なくなくなりそうなので、それでやってみます。

回答No.3

中村 拓男（@tknakamuri）

ちょっと考えればわかるけど、
以下は playSaiki()の先頭に来たときのスタックトレースもどきです。
最初ぐんぐん潜っていって、戻り際にも3個出力するので、
０～7が出力されるのは明らかでしょう。
playSaikiは pSと略記してます。

pS() counter==0
pS() 割切->pS() counter==1
pS() 割切->pS() 割切ず->pS() counter==2
pS() 割切->pS() 割切ず->pS() 割切->pS() counter==3
pS() 割切->pS() 割切ず->pS() 割切->pS() 割切ず->pS()counter==4
pS() 割切->pS() 割切ず->pS() 割切->pS() 割切ず->pS() 割切->pS() counter==5
pS() 割切->pS() 割切ず->pS() 割切->pS() 割切ず->pS() 割切ず->pS() counter==6
pS() 割切->pS() 割切ず->pS() 割切ず->pS() couter==7
pS() 割切ず->pS() counter==8

お礼

スタックトレースもどき、ありがとうございます。
おかげで、視覚的にも問題を理解することができました。
今度またこのように再帰的にプログラミングする際は、自分でしっかり流れを追えるように、スタックトレースみたいなものを書いてみます。

回答No.1

OKWavex

偶数で「2で割り切れちゃった」を表示してplaySaiki();を呼んだあとで必ず呼び元に戻って1を加えた奇数で「2で割り切れなかった」を表示するのだから、再帰的呼び出しで4まで処理したあとは呼び元に戻りながら偶数である 4 2 0 の際には常に1を加えた 5 6 7 で 「2で割り切れなかった」を表示しているだけでしょう

お礼

回答ありがとうございます。
なるほど、よび元にもどっていくと、確かに4,2,0のときの下の処理を通ってしまいますね。
理解しました、ありがとうございます。