language-agnostic - 再帰か反復か?

Question

私は再帰が大好きです。私はそれが物事を非常に単純化すると思います。別の人は同意しないかもしれません。コードも読みやすくなっていると思います。ただし、C# などの言語では、LISP ほど再帰が使用されていないことに気付きました (ちなみに、LISP は再帰のために私のお気に入りの言語です)。

C# などの言語で再帰を使用しない正当な理由があるかどうかを知っている人はいますか? 繰り返しよりも高価ですか？

score 18 · Accepted Answer

それらは反復よりも高価ですか？

はい、そうです。多くのLispバリアントは、再帰関数呼び出しの多くの使用を反復呼び出しに変換できる「テールコール最適化」のアイデアをサポートしています(これは少し単純化しています)。末尾呼び出しがサポートされていない場合、再帰関数呼び出しはスタック上のメモリを徐々に使用します。

score 16 · Accepted Answer

それらは反復よりも高価ですか？

はい、そうです。再帰では、呼び出しと戻りとともに新しいスタックフレームを作成する必要がありますが、反復では通常、比較と分岐のみが必要であり、大幅に高速化されます。ただし、コンパイラは、特定の再帰呼び出し (つまり、末尾呼び出し) に対して末尾呼び出しの最適化を実行できます。これにより、スタックフレームを再利用して、再帰呼び出しのコストを大幅に削減し、効果的に反復に変えることができます。実際、Scheme では、Scheme コンパイラが末尾呼び出しの最適化を実装する必要があります。

score 11 · Accepted Answer

Lisp や F# などの関数型言語は、多くの末尾再帰関数をループとして内部的に実装でき、関数呼び出しのスタックオーバーヘッドを回避できます。C# は末尾再帰をサポートしていませんが、F# はサポートしています。

score 11 · Accepted Answer

最新の CPU のコンパイラとアーキテクチャは、再帰ではできない多くの最適化を繰り返しで実行できます。たとえば、プロセッサが楽観的な計算を行う能力。プロセッサーが反復スペースを見つけると、それがどれくらいかかるかがわかります。最初から、次のループを開始する前に毎回確認する必要はありません。したがって、それらは操作をパイプライン化します。ほとんどの CPU は (パイプライン処理によって) 同時に複数の操作を実行できるため、再帰よりも短い時間で反復空間を解決できます。これは、CPU が実際に一度に約 4 つのループを処理しているため (4 倍のパフォーマンス向上のため)、末尾の最適化を使用した場合でも同様です。このゲインは、CPU のアーキテクチャに依存します。アーキテクチャは利益の大きな部分を占める可能性が高く、次世代 CPU はそれ以上の利益を押し上げます。

再帰の真の問題は、私たちのハードウェアが VonNeumann ベース (Turing マシンの実現可能なバリアント) であり、Lisp マシンではなく、いくつかの特殊な Lisp ハードウェアがあり、それを備えたデスクトップが見つからないことです :)

score 8 · Accepted Answer

再帰の使用には、多くの長所と短所があります。間違いなく、コードの単純さは、コードの保守性を向上させ、バグを減らすのにも役立つ最大のものです。

再帰の最大の危険は、関数スタックの制限を破るためにアルゴリズムが制御不能になったエッジケースです。一部の言語 (Progress の ABL 言語など) には、許可されるネストされた呼び出しの最高レベルのパラメーターがあります。これらは通常は低く、ミックスに再帰を追加すると、アプリケーションがその制限を破る可能性があります。

つまり、再帰は常にタイトな終了ケースで実装する必要があります。そうしないと、デバッグが非常に困難になり (予測不可能なため)、本番コードで深刻な問題が発生する可能性があります。

メモリと速度に関する懸念については、これがメソッド自体が短い (時間的に) 何度も呼び出されない限り、パフォーマンスがどうであるかは問題ではありません。

例: 再帰を使用してハードドライブのすべてのファイルとフォルダーをスキャンする場合、再帰によるパフォーマンスへの影響は、ハードドライブにアクセスしてファイルシステム情報を取得するのにかかる時間に比べればごくわずかです。この場合、おそらく反復処理よりも再帰が好まれます。

別の例: ツリー構造のノードをスキャンする場合、関数スタックをあまり使用しないため、反復プロセスがより有益である可能性があります。これは、メモリにヒットすることが少なくなり、おそらくハードウェアがより多くのキャッシュを使用できるようになることを意味します。詳細については、Robert Gould の回答を参照してください。

score 6 · Accepted Answer

アルゴリズムが再帰形式で最も自然に表現できる場合、およびスタックの深さが小さい (log(N) の範囲、つまり通常は 20 未満) 場合は、必ず再帰を使用します。(反復によるパフォーマンスの向上は、小さな定数要因になります)。

スタックが大きくなる危険性があり、言語/コンパイラ/ランタイムシステムがテールコールの最適化を保証しない場合は、再帰アルゴリズムを避ける必要があります。

score 3 · Accepted Answer

C# などの言語で再帰を使用しない正当な理由があるかどうかを知っている人はいますか? 繰り返しよりも高価ですか？

はい、C# は末尾再帰をサポートしていないためです。大規模なコレクションの単純な反復に再帰を使用する場合、再帰が深すぎると、簡単に StackOverflowException が発生し、アプリケーションがクラッシュする可能性があります。

score 2 · Accepted Answer

選択は、解決する問題だけに基づいているのではなく、使用する言語にも基づいています。C スタイルの言語 (Java、C# など) では、再帰は完全に異質に見えるので (そして再帰的に考えることができないので)、再帰を避けるというのが私の反射的な対応です。スタック乱用。しかし、再帰以外のものを使用してもほとんど意味がない問題がいくつかあります - ツリートラバーサルが良い例です。反復的な解決策は完全にもっともらしいですが、コードが大きくなり、バグが多くなり、ほぼ確実に読みにくくなります。

しかし、より動的な言語 (Lisp や Python など) は、再帰をより自然な可能性にするために多大な努力を払っています。私の個人的な回答は、問題が何であれ、最初に反復的な解決策を探すことですが、走行距離が異なると競馬になります。

結局のところ、最善の策はおそらくそれを書くことです。いずれにせよ、一度は捨てる可能性が高いです。

score 1 · Accepted Answer

再帰は、反復よりも並列化するのが（不可能/はるかに難しい）です

現代のCPUにはマルチコアがあるため、再帰用に設計した場合、 parallel.for （およびそのような手法）を使用した直接最適化ははるかに困難になります。

しかし、並列化はまだかなり曖昧であり、まだ使用している人は比較的少数です。

さらに、再帰的アルゴリズムは、同時に必要なコードと変数がわずかに少ないため、設計と検討が容易だと思います。パフォーマンスの必要がない場合は、通常、再帰を使用します。

score 1 · Accepted Answer

問題が反復に還元できる場合は、反復します。

問題が再帰を必要とする場合 (ツリーナビゲーションなど)、再帰します。

そうは言っても、私は主に C# で基幹業務アプリを作成しています。科学的プログラミングにはさまざまな要件があると確信しています。

score 1 · Accepted Answer

Scheme は、末尾呼び出しの最適化を必要とする、私が知っている唯一の Lisp 方言であり、再帰を多用する傾向があります。これを必要としない他の Lisp 方言 (Common Lisp など) では、他のどの言語よりも再帰が使用されているとは思えません。

score 0 · Accepted Answer

XSLT 変数は、一度作成されると読み取り専用になることをここで断言しておきます。このため、次のようなインデックス付き for ループで行われること

for(int i=0; i < 3; i++) doIt(i);

実際には再帰で行われます。に相当するもの

public rediculous(i) {
    doIt(i);
    if (i < 3) rediculous(i + 1);
}

ここで実際に XSLT の例を示しますが、入力するだけで Baby Jesus が泣き出してしまいます。

score 0 · Accepted Answer

再帰関数はスタックに置く必要があると思います-関数がそれ自体を呼び出すたびに、その関数の別のコピーが関数スタックに置かれます。問題は、ある時点でスタックが関数を格納するスペースを使い果たすことです。そのため、数値が大きくなると、再帰的なソリューションが機能しない可能性があります。お尻を噛まれたので知っています-free()リンクリスト全体に対して優れた再帰関数があり、作成できる最大のリンクリストでテストを行ったところ、エラーが発生しました(セグメンテーション違反だと思います-間違いなくスタックオーバーフローだったはずです:)）。

反復関数にはこれらのエラーはありません。機械語では単純な 'jmp' または 'je' などで表現されるため、関数スタックのスペースが不足することはなく、効果的にクリーンです。

これは完全に主観的な質問ですが、再帰がコンピューターに組み込まれているという事実がなければ、それははるかに優れたソリューションであると言えます。問題に対するいくつかの反復的な解決策は見苦しく見えますが、再帰的な解決策は非常にきれいで見栄えがします。しかし、それは人生です。

score 0 · Accepted Answer

リストやベクトルなどの本質的に線形のデータ構造を扱う場合、再帰よりも反復構造を好む理由の 1 つは、コードの意図をよりよく伝えることです。多くの場合、反復で十分なときに再帰が無差別に使用されると、読者がプログラムの構造を識別するためにより多くの労力が必要になります。

language-agnostic - 再帰か反復か?

14 に答える 14

Related

Reference