[javascript]再帰

復帰とは?

プログラミングでは,再帰とは,自分を定義する際に自分を再参照することである.したがって、再帰関数とは、関数が呼び出されて実行されると、関数内部で独自の再帰呼び出し(Recursive Call)が再呼び出される形式である.

Recursive vs Iterative

通常はRecursiveとIterativeが多いです.Iterativeは「繰り返す」という意味です.すなわち、for文やforEach文のような繰り返し演算をよく使用します.必ずしもそうではないが、多くの場合、「回復」で処理できる問題は「奇形器」で処理でき、逆に「回復」で処理できる問題である.プログラマの考えはどのように問題を解決するかですが、反復コードを使用するよりも再帰コードを使用するほうが理解しやすい場合があります.そのため、私たちは両方の方法を明らかにしなければなりません.

工場を求めます

再帰関数を説明するときに最も多く現れるサンプルコードは、ファクトリコードを求めることです.工場は自分から、減った数字に1を乗じた値です.例えば5!5 4 3 2 1=120です.

function factorial (n) {
var result = 1;
for (var i = n; i >= 1; i--) {
result *= i;
}
return result;
}

nから1の数にresult変数を繰り返し乗算します.乗算を行うためresult変数の初期値は1であるべきである.
これを再帰関数に変えましょう.factorial(5)からfactorial(1)を書き続けると、次のようになります.
factorial(5) = 5 4 3 2 1 = 5 * factorial(4);
factorial(4) = 4 3 2 1 = 4 factorial(3);
factorial(3) = 3 2 1 = 3 * factorial(2);
factorial(2) = 2 1 = 2 factorial(1);
factorial(1) = 1;
ここからいくつかのルールが現れます.そのルールに従ってfactorial(n)=n*factorial(n-1);になります.
これをコードで次のように表現します.

function factorial (n) {
return n * factorial(n - 1);
}

一見、上のコードはよさそうに見えますが、深刻なエラーがあります.

実際に上のコードを実行すると、ブラウザは地球の果てまで行く勢いでコードを実行し続け、ある時点でこのエラーを出力して停止します.Maximum call stack size exceeded. 最大コールスタックサイズが超過しました.これが再帰関数を使用する際に最も注意すべき部分です.
再帰関数を作成して呼び出すと、関数は自分で実行するように呼び出されます.この場合、再帰呼び出しを中断する条件文をBase caseまたはTermination caseと呼ぶように、特定の条件下で再帰呼び出しを終了する文が1つ以上存在する必要があります.
上の工場コードにはBase caseがないのでfactorial(4)、factorial(3)、...、factorial(-1), factorial(-2) ... これにより、負の領域に呼び出し続け、指定したメモリ容量を瞬時に超えて順次スタックし、上記エラーメッセージを出力します.

function factorial (n) {
if (n === 1) { // Base case, Termination case
return 1;
}
return n * factorial(n - 1);
}
factorial(3); // 6

したがって,上記のように,nが1のときに1を返す文を再帰呼び出しを終了するBase caseとして追加しなければならない.
上のコードは完璧な再帰関数を形成し、上のコードの実行順序は以下の通りです.

は、まず、パラメータnの値として3を渡す.

スタックに3を格納し、factorial(3-1)=factorial(2)を実行する.

2は

nの値で伝達される.stackに2を格納し、factorial(2-1)=factorial(1)を実行します.

1は

nの値で渡されます.nが1の場合、1が返され、関数が終了します.

階乗(1)は1を返して終了するので、2*1を演算してその値2を返します.

2と3を乗算した後、その値6を返し、すべての関数が終了します.