P29 - 斐波那契数
Fibonacci numbers
官方模块：
Problems.P29核心函数：fibonacci
← P28 按子列表长度排序 | P30 矩阵快速幂计算 →
题目描述
计算第 个斐波那契数。。
函数签名
1fibonacci :: Integral a => a -> a
实现
方法一：尾递归（累加器）
1fibonacci :: Integral a => a -> a
2fibonacci n
3 | n < 1 = error "fibonacci: index must be positive"
4 | otherwise = go n 1 1
5 where
6 go 1 a _ = a
7 go k a b = go (k - 1) b (a + b)
从 开始，往下滚动：(a, b) → (b, a+b)，重复 次。这是最实用的实现——O(n)、尾递归、整数类型通用。
方法二：递归（朴素版）
1fibonacci :: Integral a => a -> a
2fibonacci 1 = 1
3fibonacci 2 = 1
4fibonacci n = fibonacci (n - 1) + fibonacci (n - 2)
数学定义直译，但指数级复杂度。实测 fibonacci 40 就要跑十几秒——因为大量重复计算（fibonacci n 的调用次数约等于 ）。
方法三：zipWith 生成无限列表
1fibonacci :: Integral a => a -> a
2fibonacci n
3 | n < 1 = error "fibonacci: index must be positive"
4 | otherwise = fibs !! (fromIntegral n - 1)
5 where
6 fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
利用惰性求值定义一个无限斐波那契列表，通过 zipWith 自引用计算。这是 Haskell 最标志性的写法之一。
方法对比
| 方法 | 复杂度 | 特点 |
|---|---|---|
| 尾递归 | O(n) | 实用，整数类型通用 |
| 朴素递归 | O() | 定义直译，教学参考 |
| zipWith 无限列表 | O(n)（取第 n 个） | Haskell 特色，惰性求值展示 |
测试
1>>> map fibonacci [1..10]
2[1,1,2,3,5,8,13,21,34,55]
3>>> fibonacci 20
46765