java - 再帰とループのどちらがより効率的ですか?

Question

どちらが反復にとってより効率的か興味があります。文字列の解析をリストに分割するために使用しています。再帰は CPU 効率が高いですか、それともループしていますか? よりメモリ効率が良いですか？ループすることで、for、for each、do while、while、およびその他のタイプを参照しています。これらのループのうち、より効率的なのはどれですか? それともすべて平等ですか？ちょっと興味があるんだけど。

Answer 1

私によると、あなたの質問に対する最良の答えは「場合によります」です：

平均して、「分割統治」などのアルゴリズムを使用できるため、SORTED コレクションを検索すると、再帰がはるかに高速になります (この場合、コレクションを 2 つの部分に分割し、要素が存在する可能性のある半分を再帰の次のステップに送信します)。再帰は、要素が見つかった場合、またはコレクションに含まれていない場合に停止します)。

ただし、ほとんどの場合、ループは再帰よりも効率的です。単純な事実として、再帰のさまざまなレベルでダウンしている間、CPU は変数をスタックに保持し、基本的にそれをいっぱいにします。ループは、スタック内の一定量のスペースのみを使用します (通常、ただし例外が適用されます)。たとえば、再帰アルゴリズムを使用してフィボナッチ数列を計算した場合、Fibonnacci(30) の後で結果を得るには何年もかかります。そのシーケンスは、メモ化 (基本的にはループを使用) で計算できます。

覚えておくべきことの 1 つは、再帰は理解しやすく、ループよりもはるかに簡単に問題を解決するのに役立つということです。問題に対する多くのループ ベースのソリューションは、ループ アルゴリズム (メモ化) で最適化される再帰アルゴリズム (分割統治) から始まります。私はこのテーマについて授業を受けましたが、とても興味深いものでした。

私が助けてくれることを願っています。

よろしく。