基本算法实现之递推

用斐波那契数列和兔子产仔问题讲清楚递推算法的思路。

递推算法是一种理性思维模式的代表，其根据已有的数据和关系，逐步推导而得到结果。递推算法的执行过程如下：

• 根据已知结果和关系，求解中间结果。
• 判断是否达到要求，如果没有达到，则继续根据已知结果和关系求解中间结果；如果满足要求，则表示寻找到一个正确的答案。

递推算法往往需要用户知道答案和问题之间的逻辑。在许多数学问题中，都有着明确的计算公式可以遵循，因为往往可以采用递推算法来实现。

下面通过一个斐波那契数列来看一下递推的具体应用场景：

如果有一对两个月大的兔子以后每一个月都可以生一对小兔子，而一对新生的兔子出生两个月后才可以生小兔子。也就是说，1 月份出生，3 月份才可以产仔。那么假定一年内没有兔子死亡事件，那么 1 年后共有多少对兔子呢？

我们先来分析一下兔子产仔问题。来逐月看一次每月的兔子对数：

第一个月：1 对兔子；
第二个月：1 对兔子；
第三个月：2 对兔子；
第四个月：3 对兔子；
第五个月：5 对兔子；
......

从上面可以看出，从第 3 个月开始，每一个月的兔子总对数等于前两个月兔子数的总和。相应的计算公式如下：

第 n 个月兔子总数 Fn = Fn-1 + Fn-2。
这里，初始第一个月的兔子数为：F1 = 1，第二个月的兔子数为 F2 = 1。

import java.util.Scanner;

public class Solution {

    public static int fibonacci(int n) {
        int t1, t2;
        if (n == 1 || n == 2) {
            return 1;
        } else {
            t1 = fibonacci(n - 1);
            t2 = fibonacci(n - 2);
            return t1 + t2;
        }
    }


    public static void main(String[] args) {
        System.out.println("递推算法求解兔子产仔问题！");
        System.out.println("请先输入时间：");
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int num = fibonacci(n);
        System.out.println("经过" + n + "月的时间，共能繁殖成" + num + "对兔子！");
    }
}

运行结果：