IPとFPのパフォーマンスについて質問があります。n番目のフィボナッチ数を計算する関数があるとしましょう。
命令型プログラミングでは、反復法、再帰、または動的計画法を使用してn番目のフィボナッチ数を計算することを選択できます。もちろん、反復計画法と動的計画法は、漸近的に再帰する場合に比べてパフォーマンスが向上します。
関数型プログラミングでは、関係する状態がないと仮定すると、再帰的な方法でしか実行できません。
この場合、関数型プログラミングは、効率の点で（漸近的に）命令型プログラミングと比較して、常に同等または低速で実行されるという意味ではありませんか？
実際の関数型プログラミングはこの問題にどのように対処しますか？
フィボナッチ数を実装する再帰的な方法はありません。O(n) 時間で n 番目のフィボナッチ数を計算する再帰関数を簡単に作成できます。これは反復バージョンと同じように機能します (つまり、計算した最後の 2 つの数値を追跡します)。命令ループの代わりに末尾再帰。多くの関数型言語は末尾呼び出しの最適化を実行する実装を必要とするため、反復バージョンと比較して一定のオーバーヘッドさえありません。
もちろん、n 番目のフィボナッチ数をサブリニア時間で計算する方法 (閉じた形式または行列の乗算を使用) もあり、関数型言語でも命令型言語と同じように機能します。
動的プログラミングについて: 関数型言語で動的プログラミングを行うことは完全に可能です。動的プログラミング アルゴリズムは、最初に書き込まれた配列のフィールドを変更しないため、関数型プログラミングと矛盾することはありません。必要なのは、配列の構築中に配列の既に構築された部分にアクセスできることだけです。Haskell に存在する遅延配列は、これに適しています。