強制編程和函數式編程的效率

Question

我對IP和FP的性能有疑問。假設我有一個函數來計算第n個斐波納契數。

在命令式編程中，我可以選擇使用迭代方式，遞歸或動態編程來計算第n個斐波那契數。當然迭代方法和動態編程相比於遞歸漸近地執行會更好。

在函數式編程中，假設沒有涉及狀態，那麼我只能用遞歸方式來做。

在這種情況下，這並不意味着函數式編程在效率（漸近）方面總是與命令式編程相比相等或更慢？

現實世界函數式編程如何處理這個問題？

Answer 1

沒有一種遞歸方式來實現斐波納契數字。你可以很容易地編寫一個遞歸函數來計算O（n）時間內的第n個斐波納契數字 - 它的工作方式與迭代版本相同（即它會跟蹤你計算的最後兩個數字），但是使用尾遞歸而不是命令式循環。由於許多功能性語言需要執行尾部調用優化的實現，所以與迭代版本相比，甚至不會有恆定的開銷。

當然，甚至有計算次線性時間（使用閉式或矩陣乘法）的第n個斐波納契數的方法，它在函數式語言中與在命令式語言中一樣好。

關於動態編程：完全可以在功能語言中進行動態編程。由於動態編程算法在第一次寫入時不會改變陣列的場，所以這裏的函數式編程確實沒有矛盾。您所需要的只是在陣列構建時能夠訪問陣列的已構建部分。因爲它們存在於Haskell中的惰性數組適用於此。