JavaScript 末尾再帰

1. 末尾再帰の使用
2. JavaScript で末尾再帰を実装する方法

末尾再帰は、実行する最後のアクションを呼び出す関数を含むプログラミングの概念です。 これは、関数が呼び出されるたびに新しいスタック フレームを作成するのではなく、そのスタック フレームを再利用できるため、特定のアルゴリズムを最適化するための便利な手法です。

これにより、プログラムが使用するメモリの量を減らし、パフォーマンスを向上させることができます。

JavaScript では、末尾再帰はネイティブにサポートされていませんが、さまざまな手法を使用してそれを実現する方法がいくつかあります。 末尾再帰とは何か、それがどのように機能するか、JavaScript でどのように実装するかを詳しく見てみましょう。

末尾再帰の使用

特定の状況で末尾再帰が役立つ理由はいくつかあります。

1. メモリ効率: 関数が自分自身を再帰的に呼び出すと、呼び出しごとに新しいスタック フレームが作成されます。 これは、特に深くネストされた再帰呼び出しの場合、大量のメモリを使用する可能性があります。

   末尾再帰により、関数はそのスタック フレームを再利用できるため、プログラムが使用するメモリの量が削減されます。

2. パフォーマンス: 末尾再帰は、関数が複数のスタック フレームを作成および破棄するオーバーヘッドを回避できるため、パフォーマンスの点でもより効率的です。 これにより、特に入力値が大きい場合に、関数の実行が速くなります。

3. コードの単純さ: 末尾再帰により、明示的なループや反復構造が不要になるため、コードが理解しやすくなります。 これにより、コードがより簡潔になり、読みやすくなります。

JavaScript で末尾再帰を実装する方法

前述のとおり、JavaScript は末尾再帰をネイティブにサポートしていません。 ただし、さまざまな手法を使用してそれを実現する方法がいくつかあります。

例 1

1つの方法は、関数の引数に ES6 構文を使用することです。これにより、関数のパラメーターの既定値を指定できます。 これを使用して、末尾再帰を処理する単純なラッパー関数を実装できます。

function factorial(n, result = 1) {
  if (n === 1) {
    return result;
  } else {
    return factorial(n - 1, n * result);
  }
}
console.log('Factorial of 5 is ' + factorial(5));

出力：

Factorial of 5 is 120

この例では、result パラメータにデフォルト値 1 が与えられているため、関数が呼び出されたときに指定されていない場合、デフォルトで 1 になります。 これにより、factorial を呼び出し、result パラメータを 1 に設定して末尾再帰を処理する単純なラッパー関数を作成できます。

例 2

もう 1つの方法は、現在実行中の関数を参照する arguments.callee プロパティを使用することです。 これは、以下のように、実行する最後のアクションとして自分自身を呼び出す再帰関数を実装するために使用できます。

function factorial(n) {
  if (n === 1) {
    return 1;
  } else {
    return n * arguments.callee(n - 1);
  }
}
console.log('Factorial of 5 is ' + factorial(5));

出力：

Factorial of 5 is 120

このアプローチは機能しますが、いくつかの欠点があります。 まず、arguments.callee プロパティは厳密モードでは非推奨であるため、コードで厳密モードを使用すると問題が発生する可能性があります。

次に、arguments.callee プロパティが他のコードによって上書きされる可能性があり、予期しない動作を引き起こす可能性があります。

例 3

3 番目のアプローチは、トランポリン 関数を使用することです。これは、再帰関数をラップし、末尾再帰方式で呼び出すことができる高階関数です。 トランポリン機能を実装するには、次のパターンを使用できます。

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

function factorial(n, result = 1) {
  if (n === 1) {
    return result;
  } else {
    return () => factorial(n - 1, n * result);
  }
}
console.log('Factorial of 5 is ' + trampoline(factorial(5)));

出力：

Factorial of 5 is 120

この例では、factorial 関数は末尾再帰的な方法で記述されており、再帰呼び出しは関数が戻る前に実行される最後のアクションです。 次に、trampoline 関数は factorial 関数をラップし、再帰呼び出しを処理します。これにより、factorial を末尾再帰的に呼び出すことができます。

トランポリン 関数の使用は、他のアプローチよりも少し複雑になる可能性がありますが、より効率的でエラーが発生しにくいという利点があります。