performance - 命令式编程和函数式编程的效率

Question

我有一个关于IP和FP性能的问题。假设我有一个计算第 n 个斐波那契数的函数。

在命令式编程中，我可以选择使用迭代方式、递归或动态编程来计算第 n 个斐波那契数。当然，与渐近递归相比，迭代方式和动态规划会表现得更好。

在函数式编程中，假设不涉及状态，那么我只能以递归方式进行。

在这种情况下，这是否意味着与命令式编程相比，函数式编程在效率（渐近）方面的性能总是相同或更慢？

现实世界的函数式编程如何处理这个问题？

Answer 1

没有一种递归方法可以实现斐波那契数列。您可以轻松编写一个递归函数，在 O(n) 时间内计算第 n 个斐波那契数 - 它的工作方式与迭代版本相同（即它会跟踪您计算的最后两个数字），但使用尾递归而不是命令式循环。由于许多函数式语言需要实现来执行尾调用优化，因此与迭代版本相比，甚至不会有恒定的开销。

当然，甚至还有一些方法可以在亚线性时间内计算第 n 个斐波那契数（使用封闭形式或矩阵乘法），它们在函数式语言和命令式语言中的效果一样好。

关于动态编程：完全可以用函数式语言进行动态编程。由于动态编程算法在第一次编写数组时不会更改数组的字段，因此这里与函数式编程确实没有矛盾。您所需要的只是能够在构造数组时访问数组中已构造的部分。Haskell 中存在的惰性数组可以很好地解决这个问题。