今天看到一个题目
有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子对数为多少?
兔子问题
对于这个兔子问题,我一开始的解法是这样的:
1 2 3 4 5 6 7 8 9 10 11 12
| public static void rabbit2(){ int last_month_num = 0; int current_month_num = 1; int next_month_num = last_month_num + current_month_num;
for (int months = 1; months <= 12; months++) { current_month_num = next_month_num; System.out.printf("第 %d 个月兔子的对数为 %d\n",months,current_month_num); next_month_num = current_month_num + last_month_num; last_month_num = current_month_num; } }
|
我的想法是,根据题意,可以得出规律: 1、1、2、3、5、8、13…
总结规律:前两个月的数量和等于下个月
起始条件:当前月兔子对数为1的话,前一个月可以认为是0,那么下一个月就是0+1=1;
然后下一个月的值赋给当前月,当前月的值赋给上一个月
当前月兔子对数为1,前一个月为1,下一个月就是1+1=2;
当前月兔子对数为2,前一个月为1,下一个月就是2+1=3;
当前月兔子对数为3,前一个月为2,下一个月就是3+2=5;
以此类推…
程序输出:
1 2 3 4 5 6 7 8 9 10 11 12
| 第 1 个月兔子的对数为 1 第 2 个月兔子的对数为 1 第 3 个月兔子的对数为 2 第 4 个月兔子的对数为 3 第 5 个月兔子的对数为 5 第 6 个月兔子的对数为 8 第 7 个月兔子的对数为 13 第 8 个月兔子的对数为 21 第 9 个月兔子的对数为 34 第 10 个月兔子的对数为 55 第 11 个月兔子的对数为 89 第 12 个月兔子的对数为 144
|
到这里本来就结束了。但后来在网上看到另一种解法:
1 2 3 4 5 6 7 8 9 10
| public static void rabbit() { for (int months = 1; months <= 12; months++) { System.out.printf("第 %d 个月兔子的对数为 %d\n",months,getRabbits(months)); } }
private static int getRabbits(int months){ if (months == 1 || months == 2) return 1; else return getRabbits(months-1) + getRabbits(months-2); }
|
基本思想是:根据规律,如果月数是1或2,就返回1,如果是3或者以上,就返回前一个月和前两个月的和
然后要知道前一个月的数量,就又要去算前两个月和前三个月的和
要知道前两个月的数量,就又要去算前三个月和前四个月的和
一直往前算到第一个月和第二个月,得出具体的数字,然后逐步加回去
以此类推
程序输出:
1 2 3 4 5 6 7 8 9 10 11 12
| 第 1 个月兔子的对数为 1 第 2 个月兔子的对数为 1 第 3 个月兔子的对数为 2 第 4 个月兔子的对数为 3 第 5 个月兔子的对数为 5 第 6 个月兔子的对数为 8 第 7 个月兔子的对数为 13 第 8 个月兔子的对数为 21 第 9 个月兔子的对数为 34 第 10 个月兔子的对数为 55 第 11 个月兔子的对数为 89 第 12 个月兔子的对数为 144
|
两种解法,第一种可以认为是迭代的思想,而第二种则是递归的思想。
递归和迭代的区别
- 迭代:迭代是将输出做为输入,再次进行处理。
- 递归:递归是函数自己调用自己。
那么,使用递归和迭代求 1+2+3…+n 的过程是怎样的呢?
使用迭代
1 2 3 4 5
| 0+1=1 1+2=3 3+3=6 6+4=10 10+5=15
|
使用递归
1 2 3 4 5 6 7 8 9 10 11 12
| sum(5) 5+sum(4) 5+4+sum(3) 5+4+3+sum(2) 5+4+3+2+sum(1) 5+4+3+2+1+sum(0) 5+4+3+2+1+0 5+4+3+2+1 5+4+3+3 5+4+6 5+10 15
|
递归的解题思路
解决递归问题时,不要去纠结函数调用自身后的下一层函数又做了什么这些细节。
既然递归是一个反复调用自身的过程,这就说明 它每一级的功能都是一样的,因此我们只需要关注一级递归的解决过程即可。
解递归题的三部曲:
- 找整个递归的终止条件:递归应该在什么时候结束?
- 找返回值:应该给上一级返回什么信息?
- 本级递归应该做什么:在这一级递归中,应该完成什么任务?
延伸阅读: