算法基本思想---递推算法

1. 递推算法的思想

从广义的角度分析，递推思想就是通过研究问题在不同阶段的状态，找到问题在不同状态之间的关系（规律）；根据已知条件，通过状态之间的关系，从而解决问题。

问题的发展阶段，通常是有方向性的，所以递推也是有方向性的，有顺推法和逆推法两种。

2. 顺推法

顺推法就是根据已知的初始条件，通过不同转态之间的关系，推导出结果，从而解决问题。比如：已知一个事件的状态A、B、C、D、E....，求状态N。

要理解顺推法，斐波那契数列是最好的例子。

2.1 斐波那契数列

对于斐波那契数列：1、1、2、3、5、.....，我们不难发现其规律，前两项数值之和等于当前项。所以我们可以将问题进行抽象化：
对于第n项F(n)，可以得到如下定义：F(n) = F(n-1) + F(n-2)，其中F(1) = 1，F(2)=1。

通过编码，实现斐波那契数列的算法，有两种实现方法，一种是递归算法，一种是递推算法，本章讲的是递推算法，所以就使用递推算法来实现：

    public int fibonacci(int n){
        if (n == 1){
            return 1;
        }
        int f_n_1 = 1;
        int f_n_2 = 0;
        int f_n = 0;
        for (int i = 1; i < n; i ++){
            f_n = f_n_1 + f_n_2;
            f_n_2 = f_n_1;
            f_n_1 = f_n;
        }
        return f_n;
    }

可以看到，递推算法中，并没有使用递归，所以不会占用系统的栈内存空间，性能会比递归算法更加高效。

3. 逆推法

逆推法是顺推法的逆过程，根据已知的结果，通过不同的状态之间的关系，推导出初始条件，从而解决问题。

要理解逆推法，可以看下面的问题分析及解决：
问题描述：小龙的父亲供小龙读大学，一共四年（48个月），想要一次性预存一笔钱到银行中；然后小龙每个月的月初取1000块。假设银行的年利率为0.0171，若要求在第48个月小龙大学毕业时，要连本带息取出1000块，刚刚好取完，则要求一次性预存多少钱？

问题分析：最后一个月的存款为1000块，我们可以根据问题描述的条件得到倒数第二个月的剩余存款数f_47 = 1000/(1+monthRate) + 1000；同理，可以根据倒数第二个月的剩余存款数，可以算出倒数第三个月的剩余存款数。
把问题进行抽象化，f(n)表示第n个月剩余的存款数，则可以得到等式：f(n) = f(n+1)/(1+ monthRate) + 1000。 其中，0<=n<=48，f(48) = 1000。

由此等式我们可以写出对应的递推代码：

public class ReversedRecurrence {

    //存款月数
    int monthCount = 48;
    //保存每月剩余存款(第0个月到第48个月，共49个数)
    double[] money = new double[monthCount + 1];
    //每个月减少（取走）的额度
    int REDUCTION = 1000;
    //年利率
    double yearRate = 0.0171;
    //月利率
    double monthRate = yearRate / 12;

    /**
     * 求出每个月的剩余存款数，保存在数组中
     */
    public void recurrence(){
        //最后一个月剩余存款为1000
        money[48] = 1000;
        for(int i = monthCount; i > 0; i --){
            money[i -1] = money[i] / (1+ monthRate) + 1000;
        }
    }

    /**
     * 求出某个月的剩余存款数
     * @param n
     * @return
     */
    public double moneyInMonth(int n){
        double result = 1000;

        for (int i = monthCount; i > n; i --){
            result = result /(1 + monthRate) + 1000;
        }

        return result;
    }

    public void printMoney(){
        for (int i = 0; i < money.length; i ++){
            System.out.println("第" + i +"个月剩余存款为：" + money[i]);
        }
    }

    public static void main(String[] args){
        ReversedRecurrence reversedRecurrence = new ReversedRecurrence();
        reversedRecurrence.recurrence();
        reversedRecurrence.printMoney();

        System.out.println("monthInMonth 0:" + reversedRecurrence.moneyInMonth(0));
    }

}

可以看到，在逆推法中也是并没有使用递归。与顺推法比较，逆推法是知道了状态转换的结果，求转态的初始值。本质上都是找出状态之间的转换关系，然后通过已知条件解决问题。

4. 顺推法和逆推法相同点与不同点

• 相同点：都是属于递推算法，通过找到问题不同状态的关系，从而解决问题。
• 不同点：顺推法是正方向，由初始条件开始，通过状态转变关系，解决未知问题；逆推法是反方向，已知问题的结果，通过状态转换关系，推出问题的初始状态。

算法基本思想---递推算法

原文：https://www.cnblogs.com/garmentlee/p/14660682.html