JavaScriptの最後の再帰的最適化の探索


原文の住所:https://github.com/HolyZheng/...
テールの最適化
最終的な再帰性を知る前に、最後の最適化が再帰的な基礎となるため、何が最終的に呼び出されるべきですか?最後のステップで関数を呼び出します.
function f() {
  return g()
}
ps:最後のステップは、長い間他の関数を呼び出す必要があります.定数や表現ではなく、return yやreturn g()+1などです.
テールコールの最適化の原理は何ですか?
阮一峰先生のes 6の関数拡張によると、関数呼び出しはメモリに「呼び出し記録」を形成し、また「コールフレーム」とも呼ばれ、呼び出し位置や内部変数などの情報を保存します.関数Aの内部呼び出し関数Bがある場合、Aの呼び出しフレームの上方には、Bの呼び出しフレームが形成される.Bの動作が終了するまで、結果をAに戻し、Bの呼び出しフレームが消えます.関数Bの内部に関数Cが呼び出されている場合、このようにしてCの呼び出しフレームがある.すべての呼び出しフレームは、「呼び出しスタック」を形成する.
ここでの「呼び出しフレーム」と「呼び出しスタック」は、「実行環境」と「作用ドメインチェーン」ということができる.テイルコール時の関数の最後の部分が動作するので、外層の呼び出しフレームを保留する必要はなく、直接外層の呼び出しフレームを置換するので、最適化の役割を果たすことができる.
最終再帰的最適化
再帰的な再帰的な使用は便利であるが、再帰的には関数の内部で自身を呼び出し、再帰的な回数が一定のレベルに達したとき、彼が形成したコールスタックの深さは恐ろしく、「スタックオーバー」エラーが発生する可能性が高いことを知っている.最終再帰的最適化とは、最終的な呼び出しの最適化の原理を利用して再帰的な最適化を行うことである.よくある例を挙げます.フィボナッチの数値を求めます.
function fibonacci (n) {
    return n <= 1 ? 1 : fibonacci(n - 1) + fibonacci(n - 2);
}
この関数は何の最適化も行われていません.コンソールでこの関数を実行すると、fibonacci(40)は明らかに応答が遅い問題が発生しました.fibonacci(50)はブラウザカードが死亡しました.最適化
function fibonacci (n, ac1, ac2) {
    (ac1 = ac1 || 1), (ac2 = ac2 || 1);
    return n <= 1 ? ac2 :fibonacci(n - 1, ac2, ac1 + ac2);
}
この最適化には二つの点があります.まずアルゴリズムの最適化を行い、多くの繰り返しの計算を減らしました.時間の複雑さが大幅に減少しました.第二に、最終的な再帰的最適化を行いましたが、本来は「スタックオーバーフロー」は発生しません.コンソールに行ってから試してもいいです.速度の向上は一般的なものではなく、最初の最適化が発効したことを証明します.しかし、fibonacci(10000)を許可したとき、エラーが発生しました.Uncaught RangeError: Maximum call stack size exceeded、これは私たちの最終的な再帰最適化が有効ではないことを示しています.なぜですか
限界性
上記では、直接ブラウザのコンソールでfibonacci(10000)を実行すると、スタックオーバーフローが発生します.なぜですか?この点について、私は今資料を見てからの理解は、S 6はすでに最終的な再帰的最適化を実現するために提案していますが、実際に着地した後、最終的な再帰的最適化を実現したブラウザは多くないということです.したがって、私たちは最終的な再帰的な最適化を使用して、依然として「スタックオーバーフロー」のエラーが発生しています.
トランポリン関数
どうすればいいですか?もう一つの方法があります.最後の再帰的最適化の効果を達成するためには、 (trampoline)を使用します.
function trampoline(f) {
  while (f && f instanceof Function) {
    f = f();
  }
  return f;
}
コードは新しい関数を返すように変更されました.
function fibonacci (n, ac1, ac2) {
    (ac1 = ac1 || 1), (ac2 = ac2 || 1);
    return n <= 1 ? ac2 :fibonacci.bind(null, n - 1, ac2, ac1 + ac2);
}
二つの関数を結合すれば再帰的状態を循環し,スタックオーバーフローの問題も解決できる.
trampoline(fibonacci (100000))
// Infinity