これが 1 2 3 4 5 と出力される理由を誰か説明してもらえますか? 私はそれが 4 3 2 1 0 と出力されると考えましたが、私の本と日食の両方が私が間違っていると言っています。
public class whatever {
/**
* @param args
*/
public static void main(String[] args) {
xMethod(5);
}
public static void xMethod(int n){
if (n>0){
xMethod(n-1);
System.out.print(n + " ");
}
}
}
それは非常に簡単です、これらは呼び出しです
main
xMethod(5)
xMethod(4)
xMethod(3)
xMethod(2)
xMethod(1)
xMethod(0)
print 1
print 2
print 3
print 4
print 5
プリントが 1,2,3,4,5 であることがわかります
これはコール スタックの結果です。との呼び出し後は次のようになりますn = 5。この呼び出しチェーンの一番下が実際にはスタックの一番上にあるので、頭を 180 度回転させてください。
再帰呼び出しには、基本ケースと再帰ケースの 2 つのケースがあります。ここでの基本ケースは whenn == 0であり、それ以上の再帰は発生しません。
では、これらの電話から戻ってくるとどうなるでしょうか? つまり、再帰的なステップの後に何が起こるでしょうか? 始めSystem.out.print()ます。の場合、再帰と出力の両方を妨げる条件があるためn == 0、再帰も出力も行いません。
したがって、1 2 3 4 5出力として得られる理由は、呼び出しがスタックからポップされる方法によるものです。
最初に自分自身を再帰的に呼び出し、再帰呼び出しが終了したときにのみ出力します。では、どの呼び出しが最初に終了するかを考えてみてください。それは n = 0 のときです。次に n = 1 などです。
これはスタックであり、スタックから取得した後 (再帰呼び出しの後) に出力するため、順序が逆になります。スタックに置く前に印刷した場合、順序は保持されます。
System.out.print(n + " ");
xMethod(n-1);
5 4 3 2 1 が出力されます。最初に出力されてから xMethod が呼び出されるためです。
そしてあなたの場合
xMethod(n-1);
System.out.print(n + " ");
ここで終了状態に達し、ポップアップして印刷します。そう 1 2 3 4 5
再帰がどのように機能するかを説明するために、階乗計算のサンプルを見てみましょう。
int factorial(int i) {
if (i == 0) {
return 1;
}
return i * factorial(i - 1);
}
たとえば、階乗値 5 を取得してみましょう。
int result = factorial(5);
その終了値を覚えておいてください：
if (i == 0) {
return 1;
}
そして戻り値:
i * factorial(i - 1)
反復を見てください（戻り値による）：
5*factorial(4) -> 4*factorial(3) -> 3*factorial(2) -> 2*factorial(1) -> 1*factorial(0)
実際には次のとおりです。
5*(4*(3*(2*(1*factorial(0)))))
原因factorial(4) == 4*factorial(3), factorial(3) == 3*factorial(2)等
最後の反復はfactorial(0)等しいです1（終了値を見てください）。
結果として：
5*(4*(3*(2*(1*1)))) = 120
xMethodまで呼ばれnます0。スタックは になりますxMethod(5)->xMethod(4)->xMethod(3)->xMethod(2)->xMethod(1)->xMethod(0)。完了すると、printingxMethod(0)の次の行にポップします。これは、終了するまで繰り返されます。xMethod(1)1xMethod(5)
呼び出されたときにそれぞれを展開するxMethodと、コードは次のようになります。
{
nA = 5 // What n was set at first
if (nA>0){
{
// Instead of xMethod(n-1),
// we're setting nB to nA - 1 and
// running through it again.
nB = nA - 1 // nB is 4
if (nB>0){
{
nC = nB - 1 // nC is 3
if (nC>0){
{
nD = nC - 1 // nD is 2
if (nD>0){
{
nE = nD - 1 // nE is 1
if (nE>0){
{
nF = nE - 1 // nF is 0.
if (nF>0){
// This will never execute b/c nF is 0.
}
}
System.out.print(nE + " "); // prints 1
}
}
System.out.print(nD + " "); // prints 2
}
}
System.out.print(nC + " "); // prints 3
}
}
System.out.print(nB + " "); //prints 4
}
}
System.out.print(nA + " "); //prints 5
}
}
1 public static void xMethod(int n){
2 if (n>0){ //the base condition
3 xMethod(n-1); //function is again called with one value less than previous
4 System.out.print(n + " "); //now print
5 }
6 }
行番号 3 を見てください。何も出力されていませんが、関数が再度呼び出されているため、行番号 3 から、呼び出しは再び行番号 1 に到達します。つまり、n は 5 でしたが、新しい呼び出しでは n = 4 が使用され、2 行目で n が 0 未満であることが通知されるまで続行されます。
if condition が2行目で失敗した場合、5行目、6行目で関数の実行が終了したことを意味し、この時点でn = 1です。
では、どこにコールを返す必要がありますか? 最後の関数が呼び出された行 #3 で、n の値を出力する行 #4 を実行するスタックからポップアウトされます ie 1 2 3 4 5.
この xMethod(n-1); System.out.print(n + " ");
次のようにする必要があります。
System.out.print(n + " ");
xMethod(n-1);
これは正しいコードです
System.out.print(n + " ");
xMethod(n-1);