[解決済み】再帰はループより速いことがあるのか？

質問

ループよりも再帰の方がきれいな場合があることは知っていますし、反復よりも再帰を使うべき場合については何も聞いていませんし、それについてはすでに多くの質問があることも知っています。

私が聞きたいのは、再帰は これまで ループより速いのか？ループは常に新しいスタックフレームをセットアップする必要がないため、ループを改良して再帰的関数よりも高速に動作させることができるように思えます。

特に、ソート関数や二分木など、再帰がデータを処理する正しい方法であるアプリケーションにおいて、再帰がより速いかどうかを調べているのです。

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

これは、使用する言語によって異なります。 言語にとらわれない」とおっしゃるので、いくつか例を挙げてみましょう。

Java、C、Pythonでは、再帰は新しいスタック・フレームの割り当てが必要なため、（一般的な）反復に比べかなり高価です。 Cコンパイラの中には、このオーバーヘッドをなくすためにコンパイラフラグを使うことができるものがあり、これによりある種の再帰（実際にはある種のテールコール）を関数呼び出しではなくジャンプに変換することができる。

関数型プログラミング言語の実装では、反復が非常に高価で、再帰が非常に安価になることがあります。 多くの場合、再帰は単純なジャンプに変換されるが、ループ変数を変更する（これはミュータブルである）。 時々 特に複数スレッドの実行をサポートする実装では、比較的重い操作が必要になります。 ミューテーターとガベージコレクタが同時に実行されている場合、ミューテーターとガベージコレクタの間の相互作用のために、これらの環境の一部でミューテーションは高価です。

Schemeの処理系によっては、一般にループよりも再帰の方が高速になることがあるのは知っています。

要するに、答えはコードと実装に依存するのです。 好きなスタイルを使えばいいのです。 関数型言語を使っているのであれば、再帰は かもしれない の方が速い。 命令型言語を使っている場合、反復は おそらく が速くなります。 環境によっては、どちらの方法でも同じアセンブリが生成されます（それをパイプに入れて吸ってください）。

追記 環境によっては、再帰でも反復でもなく、高次の関数が最適な場合もあります。 例えば、"map", "filter", "reduce" ("fold" とも呼ばれる)などである。 これらの関数は優先的に使用され、よりクリーンであるだけでなく、環境によっては自動並列化によって最初に（あるいは唯一）ブーストされるため、反復処理や再帰処理よりも大幅に速くなることがあります。 データ並列Haskellはそのような環境の一例です。

リスト内包はもう一つの選択肢ですが、これは通常、反復、再帰、高次関数のための構文上の糖分に過ぎません。