for再帰が使用されるすべての場所でループを使用できると言うのは正しいですか? forそして、再帰が通常より遅い場合、ループ反復でそれを使用する技術的な理由は何ですか?
そして、再帰をループに変換することが常に可能である場合、それforを行うための経験則はありますか?
114645 次
10 に答える
161
呼び出し元の関数に戻ることができるように、すべての関数呼び出しをスタックに格納する必要があるため、通常、再帰は非常に遅くなります。多くの場合、スコープの分離を実装するには、メモリを割り当ててコピーする必要があります。
末尾呼び出し最適化などの一部の最適化は、再帰を高速化しますが、常に可能であるとは限らず、すべての言語で実装されているわけではありません。
再帰を使用する主な理由は次のとおりです。
- 問題に対する私たちのアプローチを模倣すると、多くの場合、より直感的になります。
- ツリーのような一部のデータ構造は、再帰を使用して探索する方が簡単です (または、いずれにしてもスタックが必要になります)。
もちろん、すべての再帰は一種のループとしてモデル化できます。これは、CPU が最終的に行うことです。そして、再帰自体は、より直接的には、関数呼び出しとスコープをスタックに入れることを意味します。しかし、再帰アルゴリズムをループ アルゴリズムに変更すると、多くの作業が必要になり、コードの保守性が低下する可能性があります。すべての最適化と同様に、プロファイリングまたは証拠によって必要であることが示された場合にのみ試行する必要があります。
于 2013-03-28T17:15:59.363 に答える
60
再帰が使用されるすべての場所で for ループを使用できると言うのは正しいですか?
はい、ほとんどの CPU の再帰はループとスタック データ構造でモデル化されているためです。
そして、再帰が通常遅い場合、それを使用する技術的な理由は何ですか?
「通常は遅い」わけではありません。再帰が正しく適用されていないため、遅くなります。その上、最近のコンパイラは再帰を尋ねることなくループに変換することに長けています。
また、再帰を for ループに変換することが常に可能である場合、それを行うための経験則はありますか?
繰り返し説明したときに最もよく理解されるアルゴリズムの繰り返しプログラムを作成します。再帰的に最もよく説明されるアルゴリズムの再帰的プログラムを作成します。
たとえば、多くのプログラミング言語では、バイナリ ツリーの検索、クイック ソートの実行、および式の解析が再帰的に説明されることがよくあります。これらも再帰的にコーディングするのが最適です。一方、階乗の計算とフィボナッチ数の計算は、反復の観点から説明する方がはるかに簡単です。それらに再帰を使用することは、大ハンマーでハエをたたくようなものです: 大ハンマーが本当に良い仕事をしたとしても、それは良い考えではありません+ .
+ Dijkstra の「Discipline of Programming」からスレッジハンマーの例えを借りました。
于 2013-03-28T17:15:03.023 に答える
30
質問 ：
また、通常、再帰が遅い場合、ループの繰り返しで再帰を使用する技術的な理由は何ですか?
答え ：
一部のアルゴリズムでは、反復的に解決するのが難しいためです。深さ優先探索を再帰的および反復的に解決してみてください。反復で DFS を解決するのは明らかに難しいという考えが得られます。
試してみるべきもう 1 つの良いこと: Merge の並べ替えを繰り返し記述してみてください。かなり時間がかかります。
質問 ：
再帰が使用されるすべての場所で for ループを使用できると言うのは正しいですか?
答え ：
はい。このスレッドには、これに対する非常に良い答えがあります。
質問 ：
また、再帰を for ループに変換することが常に可能である場合、それを行うための経験則はありますか?
答え ：
私を信じて。深さ優先検索を繰り返し解決する独自のバージョンを作成してみてください。再帰的に解く方が簡単な問題があることに気付くでしょう。
ヒント :分割統治法で解決できる問題を解決する場合は、再帰が適しています。
于 2013-03-28T17:15:38.033 に答える
1
答えのほとんどは、それを想定しているようですiterative= for loop。for ループが制限されていない場合 ( Cのように、ループ カウンターで好きなことを行うことができます)、それは正しいことです。それが実際の forループである場合 (Python や、ループ カウンターを手動で変更できないほとんどの関数型言語など)、それは正しくありません。
すべての (計算可能な) 関数は、再帰的に実装することも、whileループ (または基本的に同じことである条件付きジャンプ) を使用して実装することもできます。本当に に制限するfor loopsと、これらの関数のサブセットのみが取得されます (基本的な操作が適切な場合は、プリミティブな再帰関数)。確かに、これはかなり大きなサブセットであり、実際に遭遇する可能性のあるすべての機能がたまたま含まれています。
さらに重要なことは、多くの関数が再帰的に実装するのは非常に簡単で、反復的に実装するのは非常に難しいということです (コール スタックを手動で管理することはカウントされません)。
于 2014-02-06T23:55:57.673 に答える
0
コンピューター サイエンスの教授が昔、再帰的な解決策を持つすべての問題には反復的な解決策もあると言っていたのを覚えているようです。彼によると、再帰的な解決策は通常は遅くなりますが、反復的な解決策よりも推論とコーディングが容易な場合に頻繁に使用されます。
forただし、より高度な再帰的ソリューションの場合、単純なループを使用してそれらを常に実装できるとは思いません。
于 2013-03-28T17:15:47.113 に答える
-4
再帰+記憶は、純粋な反復アプローチと比較してより効率的なソリューションにつながる可能性があります。たとえば、これを確認してください： http://jsperf.com/fibonacci-memoized-vs-iterative-for-large-n
于 2015-11-13T14:05:04.557 に答える
-6
簡単な答え: トレードオフは、ほとんどの場合、再帰が高速であり、for ループが消費するメモリが少ないことです。ただし、通常、for ループまたは再帰を変更して実行を高速化する方法があります。
于 2013-03-29T04:36:03.357 に答える