末尾再帰

それ自体を呼び出す関数は再帰と呼ばれます。末尾がそれ自体を呼び出す場合、それは末尾再帰と呼ばれます。

再帰は、数千または数百の呼び出しフレームを同時に保存する必要があり、「スタックオーバーフロー」エラーが簡単に発生する可能性があるため、非常にメモリを消費します。ただし、末尾再帰の場合、呼び出しフレームが 1 つだけであるため、「スタックオーバーフロー」エラーは発生しません。

例 1

function factorial(n) {
  if (n === 1) return 1;  return n * factorial(n - 1);
}
 
factorial(5) // 120

ログイン後にコピー

上記のコードは階乗関数であり、n の階乗を計算するには、最大 n 件の通話レコードを保存する必要があり、計算量は O(n) です。

末尾再帰として書き換えると、呼び出し記録は 1 つだけ保持され、複雑さは O(1) になります

function factorial(n, total) {
  if (n === 1) return total;  return factorial(n - 1, n * total);
}
 
factorial(5, 1) // 120

ログイン後にコピー

例 2

もっと有名な例もあります。これは、フィボナッチ数列を計算するもので、これも完全に説明できます。末尾再帰最適化の重要性。

非末尾再帰フィボナッチ数列は次のように実装されます。

function Fibonacci (n) {
  if ( n <= 1 ) {return 1};  return Fibonacci(n - 1) + Fibonacci(n - 2);
}
 
Fibonacci(10) // 89Fibonacci(100) // 堆栈溢出, 亲测页面直接卡死, cpu: i7-4720Fibonacci(500) // 堆栈溢出

ログイン後にコピー

最適化後

function Fibonacci2 (n , ac1 = 1 , ac2 = 1) {
  if( n <= 1 ) {return ac2};  return Fibonacci2 (n - 1, ac2, ac1 + ac2);
}
 
Fibonacci2(100) // 573147844013817200000Fibonacci2(1000) // 7.0330367711422765e+208 非一般的速度Fibonacci2(10000) // Infinity

ログイン後にコピー

末尾再帰最適化

末尾再帰最適化は厳密モードでのみ有効です。つまり、通常モード、またはこの機能をサポートしていない環境でも末尾再帰最適化を使用する方法はありますか?答えは「はい」です。末尾再帰最適化を自分で実装する必要があるだけです。

原理はとてもシンプルです。末尾再帰を最適化する必要がある理由は、呼び出しスタックが多すぎるとオーバーフローが発生するため、呼び出しスタックが削減される限り、オーバーフローは発生しません。コールスタックを減らすにはどうすればよいでしょうか? 「再帰」の代わりに「ループ」を使用してください。

以下は通常の再帰関数です。

function sum(x, y) {
  if (y > 0) {    return sum(x + 1, y - 1);
  } else {    return x;
  }
}sum(1, 100000)// Uncaught RangeError: Maximum call stack size exceeded(…)

ログイン後にコピー

上記のコードでは、sum は再帰関数、パラメーター x は累積する必要がある値、パラメーター y は再帰の回数を制御します。 sum が 100,000 回再帰するように指定されると、呼び出しスタックの最大数を超えたことを示すエラーが報告されます。

トランポリン機能は、再帰的実行を周期的実行に変換できます。

function trampoline(f) {
  while (f && f instanceof Function) {
    f = f();
  }  return f;
}

ログイン後にコピー

上記は関数 f をパラメータとして受け取るトランポリン関数の実装です。 f が実行後に関数を返す限り、実行は続行されます。ここでは、関数内で関数を呼び出すのではなく、関数を返してからその関数を実行していることに注意してください。これにより、再帰的な実行が回避され、コールスタックが大きすぎる問題が解消されます。

その後、各ステップで別の関数を返すように元の再帰関数を書き直すだけです。

function sum(x, y) {
  if (y > 0) {    return sum.bind(null, x + 1, y - 1);
  } else {    return x;
  }
}

ログイン後にコピー

上記のコードでは、sum 関数を実行するたびに、それ自体の別のバージョンが返されます。

これで、トランポリン関数を使用して sum を実行するときに、コールスタックのオーバーフローが発生しなくなります。

1	`trampoline(sum(1, 100000))// 100001`

ログイン後にコピー

トランポリン関数は実際の末尾再帰最適化ではありません。以下の実装はです。

ここが重要なポイントです、退役軍人の皆さん

function tco(f) {
  var value;  var active = false;  var accumulated = [];  return function accumulator() {
    accumulated.push(arguments);//每次将参数传入. 例如, 1 100000
    if (!active) {
      active = true;      
      while (accumulated.length) {//出循环条件, 当最后一次返回一个数字而不是一个函数时, accmulated已经被shift(), 所以出循环
        value = f.apply(this, accumulated.shift());//调用累加函数, 传入每次更改后的参数, 并执行
      }
      active = false;      
      return value;
    }
  };
}var sum = tco(function(x, y) {
  if (y > 0) {    
  return sum(x + 1, y - 1)//重点在这里, 每次递归返回真正函数其实还是accumulator函数
  }  
  else {    
  return x
  }
});
 
sum(1, 100000);//实际上现在sum函数就是accumulator函数// 100001

ログイン後にコピー

上記のコードでは、tco 関数は末尾再帰的最適化の実装であり、その秘密はアクティブ状態変数にあります。デフォルトでは、この変数は非アクティブです。末尾再帰的最適化プロセスに入ると、この変数がアクティブになります。その後、再帰合計の各ラウンドは未定義を返すため、再帰実行は回避され、累積された配列には合計実行の各ラウンドのパラメータが格納され、常に価値があるため、アキュムレータ関数内の while ループが常に実行されることが保証されます。このようにして、「再帰」が「ループ」に巧みに変更され、次のラウンドのパラメーターが前のラウンドのパラメーターを置き換えて、呼び出しスタックの層が 1 つだけになるようにします。

以上がJavaScript における再帰的なスタックオーバーフローエラーの防止に関する分析の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。