问题

一对兔子从出生后第三个月开始，每月生一对小兔子。小兔子到第三个月开始，能够生育下一代的小兔子。求1年中每个月的兔子的数量。

分析

根据问题，我们可以很容易地以列表的形式获得结果，如下所示。

种类一月二月三月四月五月六月七月八月九月十月十一月十二月幼免1011235813213455成免01123581321345589总数1123581321345589144

设免子对数$y$与月份$n$的关系为$f$，即 $y=f(n)$根据以上列表，我们可以发现免子数量与月份之间的关系为: $$y=f(n)=\{\begin{array}{c}f(n-1)+f(n-2),\mathrm{i}\mathrm{f}n>2;\\ 1,\mathrm{i}\mathrm{f}n\le 1;\end{array}$$

算法实现

int f(int n){ return f(n - 1) + f(n - 2); }

讨论

使用递归是一种非常易于理解的方法，但是运算效率并不高。主要原因在于每次计算 $f(n)$ 的时候，都需要计算 $f(n-1)+f(n-2)$，时间复杂度扩展了一倍，即$O(2^n)$，运算效率。