递推算法

今天我们就来了解一个简单的算法：递推算法。通过已知条件，利用特定关系得出中间推论，直至得到结果的算法。递推算法分为顺推和逆推两种。

所谓顺推法是从已知条件出发，逐步推算出要解决的问题的方法。比如之前我们讲过的斐波拉契数列，设它的函数为f（n），已知f（1）=1，f（2）=1;f（n）=f（n-2）+f（n-1）（/1>=3。nEN）。则我们通过顺推可以知道，f（3）=f（1）+f（2）=2，f（4）=f（2）+f（3）=3……直至我们要求的解。

同理，所谓逆推法从已知问题的结果出发，用迭代表达式逐步推算出问题开始的条件，即顺推法的逆过程，称为逆推。比如最简单的求数值的题目：将一个数乘以4，再加上112，减去20，最后除以4，这时得100，那么求这个数字是多少呢？这道题目我们就可以用逆推法来求解，100～4，加上20，减去112，除以4便是结果了。

了解了递推算法的基本原理后，我们带入编程的思想来做一道题目：妈妈为小陈的四年大学学费准备了一笔存款，方式是整存零取，规定小陈每月月底取下一个月的生活费1000元。现在假设利率为1.71%，编写程序，计算妈妈最少需要存多少钱？

这道题目可以采用逆推法分析存钱和取钱的过程，因为按照月为周期取钱，所以共四年48个月，并分别对每个月进行计算。为了在第48个月大学毕业时连本带利要取1000元，这要求出前47个月时银行存款的钱数。

（1）第47个月月末存款=1000（1+0.0171/12）

（2）第46个月月末存款=（47月月末存款+1000）/（1+0.0171/12）

（3）第45个月月末存款=（46月月末存款+1000）/（1+0.0171/12）

（47）第2个月月末存款=（第三个月月末存款+1000）/（1+0.0171/12）

（48）第1个月月末存款=（第二个月月末存款+1000）/（1+0.0171/12）

本次我们使用的编程语言为c语言。很明显这道题目采用递推算法中的逆序方法，我们已知最后第48个月要取出的金额数目为1000元，我們便可以先确定一个数组为money【49】，将1000元存放在money【48】中，然后通过循环的方法，利用递归的特性，可以得出一个计算公式，这里需要注意一下，这里的利率指的是年利率，月利率需要除以12。根据计算公式可得：（每个月月末存款+1000）/（1+0.0171/12）;通过循环递推的方法从第48个月一直朝前计算，直到计算到第1个月的本末利息，便可得出最后的结果：46364.32元。

递推算法的难度不大。代码知识内容都是我们学过的，通过递推算法我们了解了存款利息的计算方式，有兴趣的同学还可以把银行贷款的计算方法变成代码，贷款和存款利息的计算方式有差别。贷款方式基本上分为两种：等额本金和等额本息。感兴趣的同学赶紧动起手来了解尝试吧。