斐波那契数列是什么

数列源自 1202 年斐波那契的兔子繁殖问题：每对成年兔每月生一对幼兔，幼兔一个月后成熟，于是每月兔对数构成 1, 1, 2, 3, 5, 8, 13, 21……递推关系 F(n) = F(n−1) + F(n−2)，其中 F(1) = F(2) = 1。通项公式（Binet 公式）用黄金比例 φ 写出：F(n) = (φⁿ − ψⁿ)/√5，ψ = −1/φ。

它与黄金比例的联姻最为著名：F(n+1)/F(n) 随 n 增大迅速逼近 φ ≈ 1.618，向日葵种子排列、松果螺旋、鹦鹉螺壳近似都呈现斐波那契式生长。编程中它是递归与动态规划的经典教材——朴素递归指数复杂度，记忆化或迭代降到线性，矩阵快速幂更能做到对数复杂度。