Haskell实现Project Euler 25的低效解法问题咨询

嘿，刚学Haskell的时候踩这个递归坑太正常了！咱们一步步拆解问题：

第一个解法的核心问题：指数级重复计算 #

你的fibGen用的是朴素递归实现：

fibGen :: Int -> Int
fibGen 0 = 0
fibGen 1 = 1
fibGen n = fibGen (n-1) + fibGen (n-2)

这种写法的致命问题在于大量重复计算：比如计算fibGen 5时，需要算fibGen 4 + fibGen 3；而计算fibGen 4又要算fibGen 3 + fibGen 2——这里fibGen 3就被算了两次。越往后，重复计算的次数会呈指数级增长：fibGen n的时间复杂度是O(2ⁿ)，当n接近生成1000位数字所需的数值（大概是第4782项），2⁴⁷⁸²的计算量完全是天文数字，跑几个小时都出结果太正常了。

雪上加霜的是你的stepper函数：

stepper n | length (show ( fibGen n )) >= 1000 = n | otherwise = stepper n + 1

每次调用stepper n都会重新调用fibGen n，相当于每一步都要从头计算一遍斐波那契数列到第n项，完全没有复用任何之前的计算结果，这进一步放大了低效问题。

第二个解法高效的原因：惰性求值+结果共享 #

而你找到的第二个解法完美利用了Haskell的惰性求值和列表共享特性：

fibs = 0:1:(zipWith (+) fibs (tail fibs))
t = 10^999
problem_25 = length w where w = takeWhile (< t) fibs

这里的fibs是一个无限列表，Haskell会按需生成每一项，而且每一项只计算一次：

• 列表前两项是0和1
• 第三项是fibs!!0 + fibs!!1（也就是0+1=1）
• 第四项是fibs!!1 + fibs!!2（1+1=2）
• 以此类推，每一项都直接复用之前已经计算好的结果，时间复杂度是O(n)的线性级别，所以速度快到瞬间出结果。

另外，用10^999作为判断条件也比length (show ...)高效得多——不需要把数字转换成字符串再统计长度，直接用数值比较就可以完成判断。

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