漫谈递归和迭代
今天看到一个题目
有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子对数为多少？
兔子问题
对于这个兔子问题，我一开始的解法是这样的：
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 个月兔子的对数为 1
第 2 个月兔子的对数为 1
第 3 个月兔子的对数为 2
第 4 个月兔子的对数为 3
第 5 个月兔子的对数为 5
第 6 个月兔子的对数为 8
第 7 个月兔子的对数为 13
第 8 个月兔子的对数为 21
第 9 个月兔子的对数为 34
第 10 个月兔子的对数为 55
第 11 个月兔子的对数为 89
第 12 个月兔子的对数为 144到这里本来就结束了。但后来在网上看到另一种解法：
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 个月兔子的对数为 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 的过程是怎样的呢？
使用迭代
0+1=1
1+2=3
3+3=6
6+4=10
10+5=15使用递归
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递归的解题思路
解决递归问题时，不要去纠结函数调用自身后的下一层函数又做了什么这些细节。
既然递归是一个反复调用自身的过程，这就说明 它每一级的功能都是一样的，因此我们只需要关注一级递归的解决过程即可。
解递归题的三部曲：
- 找整个递归的终止条件：递归应该在什么时候结束？
- 找返回值：应该给上一级返回什么信息？
- 本级递归应该做什么：在这一级递归中，应该完成什么任务？
延伸阅读：