JavaScript 再帰とループのパフォーマンス比較コード分析

パフォーマンスの点では、再帰はループよりも利点がありません。複数の関数呼び出しのオーバーヘッドに加えて、場合によっては再帰によって不必要な計算が繰り返される可能性もあります。たとえば、フィボナッチ数列を計算する再帰プログラムを考えてみましょう。 n 番目の項目 A(n) を求める場合は、n-2 番目の項目から順に各項目を繰り返し計算します。項目数が少ないほど繰り返し回数が多くなります。 i 番目の項目が計算される回数を B(i) とすると、

B(i)=1; i=n, n-1

B(i)=B(i+ 1)+B(i+ 2); i
このようにして、B(i) は興味深い逆フィボナッチ数列を形成します。 A(n) を求める場合、次のようになります:

B(i)=A(n+1-i)

別の観点から見ると、A(i) を見つけるために必要な加算の数を C(i) とします。 ) の場合、

C(i)=0; i=0, 1

C(i)=1+C(i-1)+C(i-1);

Let D( i)=C (i)+1、

D(i)=1; i=0, 1

D(i)=D(i-1)+D(i-1)

so D (i) 再びフィボナッチ数列が形成されます。そして、次のように結論付けることができます:

C(n)=A(n+1)-1

そして、A(n) は、n が大きい場合、非常に憂慮すべきものになります。ループを使用する対応するプログラムは

B(n)=1; n は任意の値

C(n)=0; n=0, 1

C(n)=n-1; n が大きい場合、上記のループを使用したプログラムは再帰を使用したプログラムよりもはるかに高速になります。

ループと同様、再帰におけるこの欠陥も補うことができます。計算された項を覚えておくだけでよく、より上位の項を見つけるときは、前の項を直接読み取ることができます。この手法は再帰で一般的であり、記憶と呼ばれます。

以下は、ストレージテクノロジーを使用してフィボナッチ数列を見つけるための再帰アルゴリズムです。
りー

以上がJavaScript 再帰とループのパフォーマンス比較コード分析の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。