JavaScriptを介した再帰とメモ化の理解

この記事では、再帰的プログラミングの使用方法、それが何であるか、およびアルゴリズムで使用するためにそれを最適化する方法を学習します。 再帰の概念を理解するために、選択するプログラミング言語としてJavaScriptを使用します。

前提条件

Big O Notationを使用して、最適化戦略を比較します。これは、ここでブラッシュアップできます。

再帰とは何ですか？

再帰とは、関数がそれ自体の内部を呼び出すときであり、無限ループを作成する可能性があります。 キャンバスアニメーションを使用したことがある場合は、再実行する前にアニメーションを更新するanimate関数を使用しているため、既に再帰を使用しています。

次の例では、数値を渡し、それを2倍にしてから、その値を再びそれ自体に渡します。 理論的には、これは永遠に続きますが、コンピューターが限られているため、通常、無限に再帰することはできません。 関数を停止するための終了条件を含めないと、too much recursionやMaximum call stack size exceededのようなエラーが発生します。次の場合、100を超えるとすぐに次のようになります。

const double = num => {
  num = num + num;
  console.log(num);

  if (num > 100) return 'Exit'; // Try removing this
  return double(num);
};

console.log(double(4));

あなたはおそらく、「それはクールですべてですが、再帰ができることのためにループを使用することはできませんか？」と考えているかもしれません。 はい、でも実際にはありません。 再帰は、さまざまな検索や並べ替えのアルゴリズムを処理したり、単純なリストよりも複雑なデータ構造をトラバースしたりする場合に便利です。 正しく実行すると、すべてのループがO（n）であるのに対し、O（log n）のようにはるかに優れたパフォーマンスを得ることができます。

メモ化

コンピュータを圧倒するのは非常に簡単であることに気付くために、再帰を長時間試す必要はありません。 これは、ほとんどの再帰関数がO（n ^ 2）またはO（n！）であるためです。 JavaScriptは、新しい再帰レイヤーが追加されるたびにコールスタックで実行されるため、JavaScriptのほとんどは冗長ですが、すべてを管理するには多くのメモリと処理能力を使用する必要があります。

フィボナッチ数列を生成するような簡単なことを試してみましょう。 フィボナッチ数列は、すべての桁がその前の2つの項目、0、1、1、2、3、5、8、12…の合計である場合です。

const fibonacci = num => {
  if (num < 2) return num;

  return fibonacci(num - 1) + fibonacci(num - 2);
};

for (let i = 0; i < 1000; i++) console.log(fibonacci(i)); // 3 minutes before page crashed...

それはただ恐ろしいです。 同じ情報の1,000層のリソースを使い果たすことは、私の比較的まともなコンピューターにとってさえも多すぎます。

代わりに、スタックが進むにつれて値を含むストレージ変数または「メモ」を追加することで、これを回避できます。 関数が実行されるたびに、その値がメモ内の対応するインデックスに追加され、次のレイヤーがそれを参照して結果を計算します。

const fibonacci = (num, memo) => {
  memo = memo || {};

  if (memo[num]) return memo[num];
  if (num < 2) return num;

  return memo[num] = fibonacci(num - 1, memo) + fibonacci(num - 2, memo);
};

for (let i = 0; i < 1000; i++) console.log(fibonacci(i)); // 143 Milliseconds

問題

これを別の再帰関数に適用してみましょう。 これは数値を取り、その階乗を出力するので、3！ 3x2x1 = 6であるため、6を返す必要があります。

const factorial = n => {
  let num = n;

  if (n === 0) return 1;
  for (let i = 0; i < n; i++) {
    num = n * factorial(n - 1);
  };

  return num;
};

console.log(factorial(3)); // 7 Milliseconds
console.log(factorial(6)); // 8 Milliseconds
console.log(factorial(9)); // 15 Milliseconds
console.log(factorial(12)); // 11,588 Milliseconds

私の場合、スタック内の各レイヤーが前のレイヤーの複雑さを処理する必要があるため、この関数の複雑さはO（n！）であるため、12を超えるとページがクラッシュします。

代わりに、メモ化して違いを確認してみましょう。

const factorial = (n, memo) => {
  memo = memo || {};

  if (memo[n]) return memo[n];
  if (n === 0) return 1;
  for (let i = 0; i < n; i++) {
    memo[n] = n * factorial(n - 1, memo);
  };

  return memo[n];
};

console.log(factorial(12));  // 4 milliseconds
console.log(factorial(120));  // 12 milliseconds
console.log(factorial(1200)); // 24 milliseconds
console.log(factorial(12000));  // 1408 milliseconds

あなたのことはわかりませんが、これは信じられないほどの改善だと思います。これで、1/8の時間で10,000倍の計算を処理できるようになりました。

まとめ

再帰は、プログラミングのキャリアを通じて繰り返し戻ったり、悩まされたりするため、非常に快適にする必要があるものの1つです。 将来、ツリーやリストをトラバースし、さまざまなデータセットを並べ替えることを学ぶために不可欠です。