再帰はループよりもはるかにクリーンな場合があることはわかっています。また、反復よりも再帰を使用すべき場合について何も尋ねているわけではありません。そのことについてはすでに多くの質問があることはわかっています。
私が尋ねているのは、再帰はループよりも速いことがあるかということです。ループが常に新しいスタック フレームを設定する必要がないため、ループを改良して再帰関数よりも高速に実行できるように常に思えます。
私が特に注目しているのは、一部のソート関数やバイナリ ツリーなど、再帰がデータを処理する適切な方法であるアプリケーションで、再帰が高速化されるかどうかです。
ベストアンサー1
これは、使用されている言語によって異なります。「言語に依存しない」と書いてあるので、いくつか例を挙げます。
Java、C、Python では、再帰は新しいスタック フレームの割り当てを必要とするため、一般的に反復に比べてかなりコストがかかります。一部の C コンパイラでは、コンパイラ フラグを使用してこのオーバーヘッドを排除できます。これにより、特定の種類の再帰 (実際には、特定の種類の末尾呼び出し) が関数呼び出しではなくジャンプに変換されます。
関数型プログラミング言語の実装では、反復処理のコストが非常に高く、再帰処理のコストが非常に低くなる場合があります。多くの場合、再帰処理は単純なジャンプに変換されますが、ループ変数 (可変) を変更すると、特に複数の実行スレッドをサポートする実装では、比較的重い操作が必要になることがあります。これらの環境の一部では、ミューテーターとガベージ コレクターが同時に実行される場合、両者の相互作用により、ミューテーションのコストが高くなります。
一部の Scheme 実装では、一般的に再帰の方がループよりも高速になることがわかっています。
簡単に言えば、答えはコードと実装によって異なります。好みのスタイルを使用してください。関数型言語を使用している場合は、再帰の方が高速になる可能性があります。命令型言語を使用している場合は、反復の方が高速になる可能性があります。環境によっては、どちらの方法でも同じアセンブリが生成されます (パイプに入れて吸ってください)。
補足:環境によっては、再帰や反復ではなく、高階関数が最適な選択肢となる場合があります。これには、「map」、「filter」、「reduce」(「fold」とも呼ばれます) が含まれます。これらは推奨されるスタイルであるだけでなく、多くの場合よりクリーンであるだけでなく、環境によっては、これらの関数が自動並列化による効果を最初に (または唯一) 得るため、反復や再帰よりも大幅に高速化できます。Data Parallel Haskell は、このような環境の例です。
リストの内包表記も別の選択肢ですが、これらは通常、反復、再帰、または高階関数の単なる構文糖です。