题目: 古典问题: 有一对兔子, 从出生后第 3 个月起每个月都生一对兔子, 小兔子长到第三个月后每个月又生一对兔子, 假如兔子都不死, 问每个月的兔子总数为多少?
具体分析如下:
- f(1) = 1(第 1 个月有一对兔子)
- f(2) = 1(第 2 个月还是一对兔子)
- f(3) = 2(原来有一对兔子, 第 3 个开始, 每个月生一对兔子)
- f(4) = 3(原来有两对兔子, 有一对可以生育)
- f(5) = 5(原来有 3 对兔子, 第 3 个月出生的那对兔子也可以生育了, 那么现在有两对兔子可以生育)
- f(6) = 8(原来有 5 对兔子, 第 4 个月出生的那对兔子也可以生育了, 那么现在有 3 对兔子可以生育)
- ..............
由以上可以看出, 第 n 个月兔子的对数为
f(n) = f(n - 1) + f(n - 2);
f(n-1) 是上个月的兔子数量, 是原来有的.
f(n-2) 是可以生育的兔子数, 即多出来的数量. 第 n-2 个月开始后的第 3 个月是第 n 个月, 此时第 n-2 个月时的兔子都可以生育了.
- public class Demo {
- public static void main(String args[]) {
- for (int i = 1; i <= 20; i++)
- System.out.println(f(i));
- }
- public static int f(int x) {
- if (x == 1||x == 2)
- return 1;
- else
- return f(x - 1) + f(x - 2);
- }
- }
手写递归
来源: http://www.bubuko.com/infodetail-2879675.html