Haskell无限斐波那契列表：高阶函数与普通递归实现性能差异问题

你的实现性能偏低的核心原因 #

• 独立的fib函数是无记忆化的朴素递归实现，时间复杂度为指数级的O(2ⁿ)。计算第n项时会产生大量重叠子问题的重复计算：比如计算fib 5需要调用fib 4和fib 3，计算fib 4时又会再次调用fib 3，n越大重复计算的量级越会呈指数增长。
• 无限列表生成逻辑没有复用之前的计算结果：每次生成第n项都要重新调用fib n从头递归，比如生成第10项要从fib 0开始算一遍，生成第11项又要从头算一遍，累积计算量会快速爆炸。

原版fibs实现性能极高的原因 #

• 利用了Haskell的惰性求值+列表共享机制，已经计算出的列表元素会被缓存，不会被重复计算。
• 实现本身是线性复杂度O(n)：zipWith (+) fibs (tail fibs)相当于把fibs列表和它的尾列表逐位相加，每一个新元素只需要用到已经计算好的前两个元素，没有任何冗余计算，因此可以瞬间生成大量项。

简易优化方向 #

如果要保留递归风格同时提升性能，可以调整逻辑复用已生成的列表结果，避免每次从头计算，示例如下：

fiblst :: [Integer]
fiblst = 1 : 1 : map (\i -> fiblst !! (i-1) + fiblst !! (i-2)) [2..]

该版本性能仍略低于原版zipWith实现，但远优于朴素递归版本。

内容的提问来源于stack exchange，提问作者Nestor Diaz