performance - 再帰か反復か?

Question

両方が同じ目的を果たすことができるアルゴリズムで、再帰の代わりにループを使用した場合、またはその逆の場合、パフォーマンスに影響はありますか? 例: 指定された文字列が回文かどうかを確認します。私は多くのプログラマーが再帰を、単純な反復アルゴリズムが法案に適合することを誇示する手段として使用しているのを見てきました。コンパイラは、何を使用するかを決定する上で重要な役割を果たしますか?

score 443 · Accepted Answer

ループにより、プログラムのパフォーマンスが向上する場合があります。再帰により、プログラマーのパフォーマンスが向上する場合があります。あなたの状況でどちらがより重要かを選択してください！

score 190 · Accepted Answer

再帰関数が末尾再帰(最後の行が再帰呼び出し)であるかどうかによっては、再帰のコストが高くなる可能性があります。末尾再帰はコンパイラによって認識され、反復的な対応するものに合わせて最適化される必要があります (コード内の簡潔で明確な実装を維持しながら)。

私は、数か月または数年でコードを維持しなければならない貧しい吸盤 (あなた自身であろうと他の誰かであろうと) にとって最も意味があり、最も明確な方法でアルゴリズムを記述します。パフォーマンスの問題が発生した場合は、コードをプロファイリングしてから、反復実装に移行して最適化を検討してください。メモ化と動的プログラミングを調べたいと思うかもしれません。

score 82 · Accepted Answer

再帰と反復を比較することは、プラスドライバーとマイナスドライバーを比較するようなものです。ほとんどの場合、頭が平らなプラスのネジを外すことができますが、そのネジ用に設計されたドライバーを使用した方が簡単ですよね?

一部のアルゴリズムは、その設計方法 (フィボナッチ数列、構造のようなツリーのトラバースなど) により、再帰に適しています。再帰により、アルゴリズムがより簡潔になり、理解しやすくなります (したがって、共有可能で再利用可能です)。

また、一部の再帰アルゴリズムは「遅延評価」を使用するため、反復アルゴリズムよりも効率的です。これは、ループが実行されるたびにではなく、必要なときにのみ高価な計算を行うことを意味します。

それはあなたが始めるのに十分なはずです。私もいくつかの記事と例を掘り下げます。

リンク 1: Haskel と PHP (再帰と反復)

これは、プログラマーが PHP を使用して大規模なデータセットを処理しなければならなかった例です。彼は Haskel で再帰を使って対処するのがいかに簡単だったかを示していますが、PHP では同じ方法を簡単に実現する方法がなかったため、反復を使用して結果を取得することを余儀なくされました。

http://blog.webspecies.co.uk/2011-05-31/lazy-evaluation-with-php.html

リンク 2:再帰をマスターする

再帰の悪い評判のほとんどは、命令型言語の高コストと非効率性に起因しています。この記事の著者は、再帰アルゴリズムを最適化して高速かつ効率的にする方法について説明しています。また、従来のループを再帰関数に変換する方法と、末尾再帰を使用する利点についても説明します。彼の締めくくりの言葉は、私が思う重要なポイントのいくつかを本当に要約しています。

「再帰的プログラミングは、保守可能で論理的に一貫性のある方法でコードを編成するより良い方法をプログラマーに提供します。」

https://developer.ibm.com/articles/l-recurs/

リンク 3:再帰はループよりも高速ですか? （答え）

これは、あなたに似たスタックオーバーフローの質問に対する回答へのリンクです。著者は、再帰またはループに関連する多くのベンチマークが言語固有のものであると指摘しています。通常、命令型言語はループを使用すると高速になり、再帰を使用すると遅くなり、関数型言語ではその逆になります。このリンクから得られる主なポイントは、言語にとらわれない/状況に盲目的な意味で質問に答えるのが非常に難しいということだと思います.

再帰はループよりも高速ですか?

score 16 · Accepted Answer

通常、再帰呼び出しごとにメモリアドレスをスタックにプッシュする必要があるため、再帰はメモリ内でよりコストがかかります。これにより、後でプログラムがそのポイントに戻ることができます。

それでも、ツリーを操作する場合のように、再帰がループよりもはるかに自然で読みやすい場合が多くあります。このような場合は、再帰に固執することをお勧めします。

score 11 · Accepted Answer

通常、パフォーマンスの低下は別の方向にあると予想されます。再帰呼び出しは、余分なスタックフレームの構築につながる可能性があります。これに対するペナルティはさまざまです。また、Python などの一部の言語 (より正確には、一部の言語の一部の実装では...) では、ツリーデータ構造の最大値を見つけるなど、再帰的に指定する可能性のあるタスクで、スタック制限にかなり簡単に遭遇する可能性があります。このような場合は、ループを使い続ける必要があります。

適切な再帰関数を作成すると、末尾再帰などを最適化するコンパイラがあると仮定して、パフォーマンスのペナルティをいくらか減らすことができます。の上。）

「エッジ」ケース (高性能コンピューティング、非常に大きな再帰の深さなど) とは別に、意図を最も明確に表現し、適切に設計され、保守可能なアプローチを採用することが望ましいです。ニーズを特定した後にのみ最適化してください。

score 8 · Accepted Answer

再帰は、複数の小さな断片に分解できる問題の反復よりも優れています。

たとえば、再帰的なフィボナッチアルゴリズムを作成するには、fib(n) を fib(n-1) と fib(n-2) に分解し、両方の部分を計算します。反復では、1 つの関数を何度も繰り返すことしかできません。

ただし、フィボナッチは実際には壊れた例であり、反復は実際にはより効率的だと思います。fib(n) = fib(n-1) + fib(n-2) および fib(n-1) = fib(n-2) + fib(n-3) であることに注意してください。fib(n-1) が 2 回計算されます!

より良い例は、ツリーの再帰アルゴリズムです。親ノードを分析する問題は、各子ノードを分析する複数の小さな問題に分解できます。フィボナッチの例とは異なり、小さな問題は互いに独立しています。

そうです - 再帰は、複数の、より小さな、独立した、同様の問題に分解できる問題の反復よりも優れています。

score 7 · Accepted Answer

再帰を使用するとパフォーマンスが低下します。これは、どの言語でもメソッドを呼び出すには多くの準備が必要になるためです。呼び出し元のコードは戻りアドレス、呼び出しパラメーター、プロセッサレジスタなどのその他のコンテキスト情報をどこかに保存し、戻り時に呼び出されたメソッドは、呼び出し元によって取得される戻り値を送信し、以前に保存されたコンテキスト情報が復元されます。反復的アプローチと再帰的アプローチのパフォーマンスの違いは、これらの操作にかかる時間にあります。

実装の観点から見ると、呼び出しコンテキストの処理にかかる時間が、メソッドの実行にかかる時間と同程度になると、実際に違いに気づき始めます。再帰メソッドの実行に呼び出し元のコンテキスト管理部分よりも時間がかかる場合は、コードが一般的に読みやすく理解しやすく、パフォーマンスの低下に気付かないため、再帰的な方法を使用してください。それ以外の場合は、効率上の理由から反復します。

score 6 · Accepted Answer

Java の末尾再帰は現在最適化されていないと思います。詳細は、LtU および関連するリンクに関するこのディスカッション全体に散りばめられています。これは、次期バージョン 7 の機能である可能性がありますが、特定のフレームが欠落するため、Stack Inspection と組み合わせた場合に特定の問題が発生するようです。スタックインスペクションは、Java 2 以降、きめの細かいセキュリティモデルを実装するために使用されています。

http://lambda-the-ultimate.org/node/1333

score 5 · Accepted Answer

多くの場合、再帰はキャッシングによって高速になり、パフォーマンスが向上します。たとえば、これは従来のマージルーチンを使用したマージソートの反復バージョンです。キャッシングによりパフォーマンスが向上するため、再帰的な実装よりも実行速度が遅くなります。

反復実装

public static void sort(Comparable[] a)
{
    int N = a.length;
    aux = new Comparable[N];
    for (int sz = 1; sz < N; sz = sz+sz)
        for (int lo = 0; lo < N-sz; lo += sz+sz)
            merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
}

再帰的な実装

private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi)
{
    if (hi <= lo) return;
    int mid = lo + (hi - lo) / 2;
    sort(a, aux, lo, mid);
    sort(a, aux, mid+1, hi);
    merge(a, aux, lo, mid, hi);
}

PS - これは、Coursera で提示されたアルゴリズムのコースで、Kevin Wayne 教授 (プリンストン大学) が語ったことです。

score 5 · Accepted Answer

反復法よりもはるかに洗練されたソリューションを提供する場合が多くあります。一般的な例はバイナリツリーのトラバーサルであるため、維持するのが必ずしも難しいわけではありません。一般に、反復バージョンは通常少し高速ですが (最適化中に再帰バージョンが置き換えられる可能性があります)、再帰バージョンの方が理解しやすく、正しく実装するのが簡単です。

score 5 · Accepted Answer

再帰は、状況によっては非常に便利です。たとえば、階乗を見つけるためのコードを考えてみましょう

int factorial ( int input )
{
  int x, fact = 1;
  for ( x = input; x > 1; x--)
     fact *= x;
  return fact;
}

再帰関数を使って考えてみましょう

int factorial ( int input )
{
  if (input == 0)
  {
     return 1;
  }
  return input * factorial(input - 1);
}

この 2 つを観察すると、再帰が理解しやすいことがわかります。しかし、注意して使用しないと、エラーが発生しやすくなります。を逃しif (input == 0)た場合、コードはしばらく実行され、通常はスタックオーバーフローで終了するとします。

score 4 · Accepted Answer

再帰を使用すると、各「反復」で関数呼び出しのコストが発生しますが、ループでは、通常支払うのはインクリメント/デクリメントだけです。したがって、ループのコードが再帰ソリューションのコードよりもそれほど複雑でない場合、通常、ループは再帰よりも優れています。

score 4 · Accepted Answer

言語によって異なります。Java では、ループを使用する必要があります。関数型言語は再帰を最適化します。

score 4 · Accepted Answer

再帰と反復は、実装するビジネスロジックによって異なりますが、ほとんどの場合、同じ意味で使用できます。ほとんどの開発者は、再帰の方が理解しやすいため、再帰を使用します。

score 3 · Accepted Answer

リストを繰り返し処理している場合は、必ず繰り返し処理してください。

他のいくつかの回答では、(深さ優先) ツリートラバーサルについて言及されています。非常に一般的なデータ構造に対して行うのは非常に一般的であるため、これは本当に素晴らしい例です。再帰は、この問題に対して非常に直感的です。

ここで「検索」メソッドをチェックしてください: http://penguin.ewu.edu/cscd300/Topic/BSTintro/index.html

score 3 · Accepted Answer

再帰は、反復の可能な定義よりも単純です (したがって、より基本的です)。コンビネータのペアだけでチューリング完全システムを定義できます(そうです、再帰自体でさえ、そのようなシステムでは派生的な概念です)。ラムダ計算は、再帰関数を特徴とする同様に強力な基本システムです。しかし、反復を適切に定義したい場合は、最初にもっと多くのプリミティブが必要になります。

コードに関しては - いいえ、ほとんどのデータ構造は再帰的であるため、再帰的なコードは純粋に反復的なコードよりも理解しやすく、維持するのが実際にははるかに簡単です。もちろん、それを正しく行うには、少なくとも、すべての標準的なコンビネータとイテレータを適切な方法で取得するために、高次関数とクロージャをサポートする言語が必要です。もちろん、C++ では、複雑な再帰的なソリューションは、 FC++などのハードコアユーザーでない限り、見栄えが悪くなります。

score 2 · Accepted Answer

（テールではない）再帰では、関数が呼び出されるたびに新しいスタックなどを割り当てるためのパフォーマンスヒットがあると思います（もちろん言語に依存します）。

score 2 · Accepted Answer

再帰？どこから始めればよいか、ウィキは「それは自己類似の方法でアイテムを繰り返すプロセスです」と教えてくれます

私が C をやっていた頃、C++ の再帰は「末尾再帰」のような神からの贈り物でした。また、多くの並べ替えアルゴリズムで再帰が使用されていることもわかります。クイックソートの例: http://alienryderflex.com/quicksort/

再帰は、特定の問題に役立つ他のアルゴリズムと同様です。おそらく、すぐに、または頻繁に使用法を見つけることはできないかもしれませんが、それが利用可能であることを嬉しく思う問題があるでしょう.

score 2 · Accepted Answer

それは「再帰の深さ」に依存します。これは、関数呼び出しのオーバーヘッドが合計実行時間にどの程度影響するかによって異なります。

たとえば、古典的な階乗を再帰的に計算することは、次の理由により非常に非効率的です。 - データオーバーフローのリスク - スタックオーバーフローのリスク - 関数呼び出しのオーバーヘッドが実行時間の 80% を占める

チェスのゲームで位置分析のための最小-最大アルゴリズムを開発している間、後続の N の動きを分析し、「分析の深さ」を再帰的に実装できます (私が行っているように ^_^)

score 1 · Accepted Answer

マイクは正しいです。末尾再帰は、JavaコンパイラまたはJVMによって最適化されていません。あなたは常に次のようなものでスタックオーバーフローを取得します：

int count(int i) {
  return i >= 100000000 ? i : count(i+1);
}

score 1 · Accepted Answer

反復がアトミックであり、新しいスタックフレームをプッシュして新しいスレッドを作成するよりも桁違いにコストがかかり、複数のコアがあり、ランタイム環境がそれらすべてを使用できる場合、再帰的アプローチは、マルチスレッド。反復の平均回数が予測できない場合は、スレッドの割り当てを制御し、プロセスがあまりにも多くのスレッドを作成してシステムを占有するのを防ぐスレッドプールを使用することをお勧めします。

たとえば、一部の言語では、再帰的なマルチスレッドマージソートの実装があります。

ただし、繰り返しますが、マルチスレッドは再帰ではなくループで使用できるため、この組み合わせがどれだけうまく機能するかは、OS とそのスレッド割り当てメカニズムを含むその他の要因に依存します。

score 1 · Accepted Answer

許可されたスタックサイズによっては、深すぎる再帰を使用するとスタックオーバーフローが発生することに注意する必要があります。これを防ぐには、再帰を終了する基本ケースを必ず提供してください。

score 0 · Accepted Answer

私の知る限り、Perl は末尾再帰呼び出しを最適化しませんが、偽造することはできます。

sub f{
  my($l,$r) = @_;

  if( $l >= $r ){
    return $l;
  } else {

    # return f( $l+1, $r );

    @_ = ( $l+1, $r );
    goto &f;

  }
}

最初に呼び出されると、スタックにスペースが割り当てられます。次に、引数を変更し、スタックに何も追加せずにサブルーチンを再起動します。したがって、自分自身を呼び出したことがないふりをして、反復プロセスに変更します。

my @_;" " または " "がないことに注意してくださいlocal @_;。使用すると機能しなくなります。

score -1 · Accepted Answer

再帰に対する一種の「二重」である「誘導」によってHaskellデータ構造を設計することによってあなたの質問に答えるつもりです。そして、この二重性がどのように素晴らしいものにつながるかを示します。

単純なツリーのタイプを紹介します。

data Tree a = Branch (Tree a) (Tree a)
            | Leaf a
            deriving (Eq)

この定義は、「ツリーはブランチ（2つのツリーを含む）またはリーフ（データ値を含む）」と読むことができます。したがって、葉は一種の最小限のケースです。木が葉でない場合は、2本の木を含む複合木である必要があります。これらは唯一のケースです。

木を作りましょう：

example :: Tree Int
example = Branch (Leaf 1) 
                 (Branch (Leaf 2) 
                         (Leaf 3))

ここで、ツリーの各値に1を追加するとします。これを行うには、次の呼び出しを行います。

addOne :: Tree Int -> Tree Int
addOne (Branch a b) = Branch (addOne a) (addOne b)
addOne (Leaf a)     = Leaf (a + 1)

まず、これは実際には再帰的な定義であることに注意してください。データコンストラクターのBranchとLeafをケースとして使用します（Leafは最小限であり、これらが唯一の可能なケースであるため）、関数が終了することは確実です。

addOneを反復スタイルで作成するには何が必要ですか？任意の数のブランチへのループはどのようになりますか？

また、この種の再帰は、「ファンクター」の観点から、しばしば除外することができます。次のように定義することで、ツリーをファンクターにすることができます。

instance Functor Tree where fmap f (Leaf a)     = Leaf (f a)
                            fmap f (Branch a b) = Branch (fmap f a) (fmap f b)

と定義：

addOne' = fmap (+1)

代数的データ型のカタモルフィズム（またはフォールド）など、他の再帰スキームを除外できます。カタモルフィズムを使用して、次のように書くことができます。

addOne'' = cata go where
           go (Leaf a) = Leaf (a + 1)
           go (Branch a b) = Branch a b

score -2 · Accepted Answer

スタックオーバーフローは、メモリ管理機能が組み込まれていない言語でプログラミングしている場合にのみ発生します。それ以外の場合は、関数 (または関数呼び出し、STDLbs など) に何かがあることを確認してください。再帰がなければ、Google や SQL のようなもの、または大規模なデータ構造 (クラス) やデータベースを効率的にソートする必要がある場所を使用することはできません。

ファイルを繰り返し処理したい場合は、再帰が最適です。?grep *' が機能します。特にパイプを使用した場合の二重再帰のようなものです（ただし、他の人が使用できるようにする場合は、多くの人が好きなように大量のシステムコールを実行しないでください）。

高水準言語や clang/cpp でさえ、バックグラウンドで同じように実装する場合があります。

performance - 再帰か反復か?

30 に答える 30

反復実装

再帰的な実装

Related

Reference