漫谈递归和迭代

1195字约4分钟

数据结构和算法

2018-03-01

今天看到一个题目

有一对兔子，从出生后第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

递归的解题思路

解决递归问题时，不要去纠结函数调用自身后的下一层函数又做了什么这些细节。

既然递归是一个反复调用自身的过程，这就说明 它每一级的功能都是一样的，因此我们只需要关注一级递归的解决过程即可。

解递归题的三部曲：

找整个递归的终止条件：递归应该在什么时候结束？
找返回值：应该给上一级返回什么信息？
本级递归应该做什么：在这一级递归中，应该完成什么任务？