再帰が使用される場所ならどこでもforループを使用できるというのは正しいでしょうか? また、再帰は通常より遅い場合、forループ反復よりも再帰を使用する技術的な理由は何ですか?
再帰をforループに変換することが常に可能である場合、それを実行するための経験則的な方法はありますか?
ベストアンサー1
再帰は通常、呼び出し元の関数に戻ることができるようにすべての関数呼び出しをスタックに格納する必要があるため、はるかに遅くなります。多くの場合、スコープ分離を実装するには、メモリを割り当ててコピーする必要があります。
いくつかの最適化、例えば末尾呼び出し最適化、再帰を高速化しますが、常に可能であるとは限らず、すべての言語で実装されているわけではありません。
再帰を使用する主な理由は
- 多くの場合、問題に対する私たちのアプローチを模倣すると、より直感的になります
- ツリーのような一部のデータ構造は再帰を使うと探索しやすくなる（いずれにしてもスタックが必要になる）
もちろんすべての再帰できる一種のループとしてモデル化する必要があります。これが CPU が最終的に行うことです。そして、再帰自体は、より直接的には、関数呼び出しとスコープをスタックに配置することを意味します。ただし、再帰アルゴリズムをループアルゴリズムに変更するには、多くの作業が必要になり、コードの保守性が低下する可能性があります。すべての最適化と同様に、プロファイリングまたは証拠によって必要であることが示された場合にのみ試行する必要があります。