算法思想学习--递推

分为两类：

1. 顺推法：从已知条件出发，逐步推算出要解决问题的方法。
2. 逆推法：从已知结果出发，用迭代表达式逐步推算出问题开始的条件，即顺推法的你过程。
   来举两个例子：

题目 （顺推法）

斐波那契数列（Fibonacci sequence），又称黄金分割数列

求斐波那契数列的第 n 项。

public class Fibonacci {
	public int Fn(int n) {
		int F1 = 0;
		int F2 = 1;
		int sum = 0;
		if(n == 0){return 0;}
		if(n == 1) {return 1;} 
		for (int i = 2;i < n;i++ ) {
			sum = F1 + F2;
			F1 = F2;
			F2 = sum;
		}
		return sum;
	}
}

题目 （逆推法）

银行存款问题
问题描述：母亲为儿子sun 4年的大学生活准备了一笔存款，方式是整取零存，规定sun 每个月月底取下一个月的生活费。假设银行年利息为1.71%,计算该母亲每个月至少要存入多少钱？这是原题，可是我觉得应该是母亲要至少要存入多少钱，没有“每个月”，如有错误，还请各位大佬提醒，我加以改正

算法分析：可采用逆推法分析存钱和取钱的过程，因为按照月为周期取钱，所以4年可以分为48个月，并对每个月进行计算。
如果第48个月后sun大学毕业连本带息要取1000元，则要求第47个月银行的存钱金额为：
第47个月月末存款=1000/(1+0.0172/12);
第46个月月末存款=（第47存款+1000）/(1+0.0172/12); //为什么加第47个月的存款呢，我们第46个月要取出1000块钱还要剩余第47个月的存款，也就是说我们取钱的时候是1000+第47个月的存款。
第45月末存款=（第46存款+1000）/(1+0.0172/12);//以此类推
…….
第2月月末存款=（第3月月末存款+1000）/(1+0.0172/12);
第1月月末存款=（第2月末存款+1000）/(1+0.0172/12);
代码实现：

public class BankAccount {
	private final static double FETCH = 1000;
	private final static double RATE = 0.0171;
	public static void main(String[] args) {
		BankAccount account = new BankAccount();
		account.Count();
	}
	public void Count() {
	    double[] list = new double[48];
	    list[47] = FETCH;
	    System.out.println("第48个月月末存款为"+list[47]);
		for(int i = 46; i >= 0 ; i--) {
			list[i] = (list[i+1] + FETCH)/(1+RATE/12);
			int n = i+1;
			System.out.println("第"+n+"个月月末存款为"+list[i]);
		}
	}
}

效果：