[解決済み] 再帰と反復

質問

再帰が使われるところではどこでも for ループが使用される可能性があるというのは正しいでしょうか。また、もし再帰が通常より遅いのなら、それを for ループの反復を使用する技術的な理由は何ですか？

また、もし再帰を常に for ループに変換できるのであれば、それを行うための経験則はあるのでしょうか？

どのように解決するのですか？

再帰処理は、呼び出し元の関数に戻るために、すべての関数呼び出しをスタックに格納する必要があるため、通常、非常に遅くなります。多くの場合、スコープアイソレーションを実装するために、メモリを割り当てたりコピーしたりする必要があります。

いくつかの最適化、たとえば テールコールの最適化 のように、再帰を高速化する最適化もありますが、常に可能とは限りませんし、すべての言語で実装されているわけではありません。

再帰を使用する主な理由は以下の通りです。

• 問題のアプローチを模倣する場合、多くの場合においてより直感的であること
• 木のようないくつかのデータ構造は、再帰を使用して探索する方が簡単であること (あるいは、どのような場合でもスタックが必要であること)

もちろん、すべての再帰は は は一種のループとしてモデル化することができます。そして再帰そのものは、より直接的には、関数呼び出しとスコープをスタックに置くことを意味します。しかし、再帰アルゴリズムをループするものに変更するには多くの作業が必要で、コードの保守性が低下するかもしれません。すべての最適化について、プロファイリングまたは証拠によってそれが必要であることが示された場合にのみ、それを試みる必要があります。