この再帰関数が 5 * 4 * 3 * 2 * 1 を生成して 120 を取得する方法を誰か説明できますか?
var factorial = function(n){
if (n === 0)
return 1;
else
return n * factorial(n - 1);
};
factorial(5); // spits out 120
例のように 5 like を使用すると、else ステートメントに到達すると、
return n * factorial(n - 1);
「階乗関数 (5-1) を掛けた 5 を返す」に変換します。5回…
この再帰関数が「for ループ」のように感じるのは間違っていますか?
いいえ、再帰とループには多くの共通点があります。特に、両方に終了条件があることが非常に重要です。:-) この場合、その終了条件はn === 0.
これを理解する最善の方法は、デバッガーでコードを 1 ステップ実行することです。ブラウザには 1 つあるため、そのコードをページに配置してロードし、ウォークスルーすることができます。
開始するには:
を呼び出しますfactorial(5)。nではないので=== 0、( )factorialで自分自身を呼び出しますn - 14
これで、1 つのレベルを再帰し、実行していますfactorial(4)(への呼び出しはfactorial(5)まだ返されておらず、待機中です)。nではないので、=== 0呼び出して、それが戻るfactorial(3)のを待ちます。
...すすぎ、factorial(0)呼ばれるまで繰り返します。が true であるためn === 0(その時点で、未処理の呼び出しが 5 つありfactorial、積み上げられている)、factorial(0)が返さ1れ、積み上げられた呼び出しの巻き戻しを開始できます。
取得した結果に( )のコピーをfactorial(1)掛けて、それを返すことで終了できます。factorial(0)n1
...これでfactorial(2)終了し、それを掛けます2...
...すすぎの繰り返し...
または、入れ子 (再帰) を示す別の言い方をすると:
階乗(5)
戻り値 5 * 階乗 (4)
戻り値 4 * 階乗 (3)
戻り値 3 * 階乗 (2)
戻り値 2 * 階乗 (1)
1 *階乗(0)を返す
リターン 1
そして、十分な図を取得できないため (少なくとも私は取得できません):
factorial(5) factorial(4) factorial(3) factorial(2) factorial(1) factorial(0)
コール ---------->
コール ---------->
コール ---------->
コール ---------->
コール ----------->
n は 0 なので、
1 を返します
| |
1 * 1<-----------+ を返します
= 1
| |
2 * 1を返します<------------+
= 2
| |
3 * 2を返します<------------+
= 6
| |
4 * 6<------------+ を返します
= 24
| |
5 * 24<-----------+ を返します
= 120
結果: 120
補足: この関数では負の数を使用できません。おそらく最初はガードを使用できます...
n変更点:
5 * factorial(5-1) = 5 * 4 * factorial(4-1) = 5 * 4 * 3 * factorial(3-1) = 5 * 4 * 3 * 2 * factorial(1-1) = 5 * 4 * 3 * 2 * 1
また、この関数をより良くするために、1 の階乗は 1 であるため、nが に等しいときに停止することができます。1
var factorial = function(n){
if (n === 1 || n === 0)
return 1;
else
return n * factorial(n - 1);
};
この関数は次のように述べています: factorial(5) を計算したい場合、それは本当に
5 * factorial(4)
factorial(4) を計算したい場合、それは実際には 4 * factorial(3) です。
5 * 4 * factorial(3)
factorial(3) に関することは、実際には 3 * factorial(2) であるということです。
5 * 4 * 3 * factorial(2)
等々。しかし、factorial(0) に到達すると、関数は最終的に停止し (if n == 0大文字と小文字が区別されるため)、それ以上の再帰なしで 1 を返します。だからあなたは得る
5 * 4 * 3 * 2 * 1
return n * factorial(n - 1)(最初の実行で) "return (5 * 4!)" に変換されます。5回では何も起こりません。
例のように 5 like を使用すると、else ステートメントに到達すると、
n * factorial(n - 1) を返します。
「階乗関数 (5-1) を掛けた 5 を返す」に変換します。5回…
いいえ、それは「階乗関数 (n-1) で乗算された n を返す」に変換されます (n は 5 から始まるため、5 回減少し、0 に達するまで else 句に入ります)。
n が 0 になるまで、これらの手順をすべて繰り返します。その後、if 句は true になり、関数は 1 を返します。
したがって、factorial(0) からは 1 が返されます。Factorial(1) は 1 * factorial(0) を返すため、1 * 1 = 1 になります。
Factorial(2) は 2 * factorial(1) を返すため、2 * 1 = 2 となります。
Factorial(3) は 3 * factorial(2) を返すため、3 * 2 = 6 となります。
Factorial(4) は 4 * factorial(3) を返すため、4 * 6 = 24 になります。
Factorial(5) は 5 * factorial(4) を返すため、5 * 24 = 120 になります。