java算法

    递推算法是常用的算法思想，在数学计算等方面有着广泛的应用。递推算法适合有着明显公式的规律场合。

一、递推算法基本思想

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

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

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

二、递推算法实例

    递推算法是基本的算法思想，常用于数学相关的场合。虾米那通过一个简单的数学例子来分析递推算法的应用。

    数学里面的斐波那契数列便是一个使用递推算法的经典例子如下：

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

1、递推算法

        先来分析一下兔子产仔问题，逐月分析每月兔子对数。

        从上述内容可以看出，从第3个月开始，每个月的兔子总对数等于前两个月兔子数的总和。相应的计算公式（Fn=F(n-1)+F(n-2)）,这里的n是第n个月，这里初始第1个月的兔子数为F1=1,F2=1。实例如下：

1public static int fibonacci(int n){
2    int t1,t2;
3    if (n == 1 || n == 2){
4        return 1;
5    }else{
6        t1 = fibonacci(n-1);//递归调用
7        t2 = fibonacci(n-2);//递归调用
8        int num = t1 + t2;
9        return num;
10    }
11}

2、递推算法求解兔子产仔问题

        根据上述通用的兔子产仔问题算法，可以求解任意该类问题。下面给出完整的兔子产仔问题求解代码

1public class mian1 {
2    /**
3     * 如果一对两个月大的兔子以后每一个月都可以生一对小兔子，而一对新生的兔子出生两个月后才可以生小兔子。
4     * 也就是说1月份出生，三月份才可产仔。那么假定一年内没有发生兔子死亡事件，那么1年后共有多少对兔子呢？
5     */
6    public static int fibonacci(int n){
7        int t1,t2;
8        if (n == 1 || n == 2){
9            return 1;
10        }else{
11            t1 = fibonacci(n-1);//递归调用
12            t2 = fibonacci(n-2);//递归调用
13            int num = t1 + t2;
14            return num;
15        }
16    }
17    public static void main(String[] args) {
18        System.out.print("请先输入月份:");
19        Scanner scanner = new Scanner(System.in);
20        int n = scanner.nextInt();
21        int num = fibonacci(n);
22        System.out.println("经过"+n+"月的时间,共繁殖了"+num+"对兔子！");
23
24    }
25}

    效果如下：

1请先输入月份:12
2经过12月的时间,共繁殖了144对兔子！