Javaでの再帰どのように動作するのですか？

Question

次のコードで再帰文の動作を説明してください。

int factR(int n) { 
    int result; 

    if(n==1) return 1; 

    result = factR(n-1) * n; 
    return result; 
} 

私の理解では、ということである：上記の文で

がfactR(n-1)方法は最後まで自身を呼び出します。 6の階乗を求めたいとします。この階乗は引数としてこのメ​​ソッドに送られます。それはパラメータnとして受信され、nの値がチェックされます。 1の場合は1が返されます。しかし、1でない場合、6の場合のように、再帰文が実行されます。

私が直面する問題は、最初にn-1が5になり、値6を保持するnで乗算され、30になります。

n-1がそれ自身を呼び出して今度はnと乗算され、IFが値 "6"を保持し、4 * 6 = 24となると私は間違っていると考えます。このようにすれば、次の呼び出しでは のプロセスはn-1となり、同じ値、すなわち6を保持する3 * nとなり、3 * 6 = 18となるため、次の呼び出しが発生し、n-1私が掛け合わせると2になり、値0を保持していると仮定すると、n-1はn-1つまり6-1を減らすことが明らかです= 5、次に5-1 = 4、4-1 = 3、3-1 = 2、および2-1 = 1である。しかし、質問はnの値になります。この値は、メソッドがそれ自身を呼び出すたびに乗算されますか？

「n-1」が5になり、次に6が30に乗算され、30が「n」に格納され、次のコールで5-1 = 4 * 30 = 120 3-1 = 2 * 360 = 720、最後に1 * 720 = 720の場合、Javaは結果の値を変数nに戻す方法をどのように決定しますか？

私は変数resultの値がメソッドは、このように、このように自分自身を呼び出すたびにあるかどうか確認するために別のステートメントを配置する場合：

int factR(int n) { 
    int result; 

    if(n==1) return 1; 

    result = factR(n-1)*n ; 
    System.out.println(result); 
    return result; 
} 

その後、私はこの出力を得る：

2 
6 
24 
120 
720 
Factorial of 6 is 720 

最初の呼び出しで2がどのように生成されるのか分かりません。値2、次に6,24,120、および720はどこから来ますか？私はコードの作業にひどく悩まされていると思う。

Answer 1

方法は本当にnの階乗を見つけるために、このような構造にする必要があります。

int factorial(int n) 
{ 
    if (n == 1) 
     return 1; 

    return n * factorial(n - 1); 
} 

彼らは「ので、それは再帰関数の内部で新しい変数をインスタンス化するために、私の意見では、非常に良いアイデアではありませんスコープのため各コールでリセットされるだけです。

Answer 2

nは、お使いの関数のローカル変数です。これは、あなたの関数へのすべての呼び出し（再帰でもそうでなくても）は、その関数のパラメータを含む新しい変数nを取得することを意味します。値型であるため、コピーされ、元の値への参照ではありません。したがって、1回の呼び出しでそれを変更しても、他の（再帰的な）呼び出しの変数には影響しません。

この結果、関数はまず6のコピーを取得し、その関数の次の呼び出しのコピーとして1を減らします。その呼び出しは6-1=5という "コピー"を取得し、再びそれを減らします。 1に達すると、1も返されます。その後、呼び出しスタックを介して再度処理を行い、最後の呼び出しの結果とこの呼び出しのローカル変数を乗算します。したがって1は2で乗算され、返されます。その結果は3などと掛け合わされます。最後に、階乗で終わります。

Answer 3

終了ステートメントに達するまで関数が展開されます（n == 1）。したがって、n = 6とし、factR(n-1) * n = factR(5) * 6がありますが、factR(5)とは何ですか？まあそれはちょうどfactR(4) * 5であるので、それはfactR(5) * 6 = (factR(4) * 5) * 6を参照してください。今factR(1) = 1ことに注意してください、と私たちはJavaで

factR(6) = factR(5) * 6 
     = (factR(4) * 5) * 6 
     = ((factR(3) * 4) * 5) * 6 
     = (((factR(2) * 3) * 4) * 5) * 6 
     = ((((factR(1) * 2) * 3) * 4) * 5) * 6 
     = ((((1 * 2) * 3) * 4) * 5) * 6 
     = (((2 * 3) * 4) * 5) * 6 
     = ((6 * 4) * 5) * 6 
     = (24 * 5) * 6 
     = 120 * 6 
     = 720 

Answer 4

を取得し、我々はスタックと呼ばれるものを持っています。

メソッドが別のメソッドによって呼び出されるたびに、スタックに追加されます。

________ 
|factR(1)| = <prints nothing> 
________ 
|factR(2)| = 2 
________ 
|factR(3)| = 6 
________ 
|factR(4)| = 24 
________ 
|factR(5)| = 120 
________ 
|factR(6)| = 720 

これは基本的にfactR(6)メソッドが完了するために、factR(5)は、完了する必要がありfactR(5)が完了するのを、factR(4)はそうで完了しなければならないことを意味します。

factR(6)の場合は、factR(5)に電話をかけてから結果が異なるため、完了するまでお待ちください。

しかし、factR(5)では、あなたも再帰呼び出しを行い、あなたは待たなければなりません。

というように、私達はちょうどfactR(2)それまでなので、上の結果をプリントアウトし、その親メソッドに結果を返す、とすることができ、完全なfactR(1) 1.

を返します。これは、制限factR(1)を打つまでfactR(6)が出力され、結果が返されます