递推算法是一种简单的算法，通过已知条件，利用特定关系得出中间推论，逐步递推，直至得到结果为止。
递推算法可分为顺推法和逆推法两种
顺推法：从已知条件出发，逐步推算出要解决问题的方法。例如，斐波那契数列就可以通过顺推法不断递推算出新的数据。
逆推法：从已知的结果出发，用迭代表达式逐步推算出问题开始的条件，即顺推法的逆过程。
顺推实例：斐波那契数列
欧洲数学家斐波那契在他的著作《算盘书》中出了一个有趣的题目：如果一对兔子每月能生一对小兔子，而每对小兔子在它出生后的第3个月里，又能开始生一对小兔子，假定在不发生死亡的情况下，由一对初生的兔子开始，1年后能繁殖出多少对兔子？
随月份增加，可以递推出兔子的总数是：1,1,2,3,5,8,13,21……这个数列有十分明显的特点：从第3个数开始，当前数据项为前面相邻两项之和。
这样的数列称为斐波那契数列：fib[i] = fib[i-1] + fib[i-2]
逆推实例：该存多少钱
父亲准备为小龙的四年大学生活一次性在银行储蓄一笔钱，使用整存零取的方式，控制小龙每个月月底只能提取1000元给下个月使用。假设银行一年整存零取的年利息为1.71%，请编程计算出父亲至少需要一次性存入多少钱才够小龙四年生活（四年的利息也计算在内）。
解题思路：
分析存钱和取钱的过程，可以采用逆推的方法。因为是按月取钱，因此把四年分为48个月，每个月分别进行计算。
若在第48个月小龙连本带息要取出1000元，则要求第47个月时银行存款的具体数额为(年利率除以12为月利率)：
第47个月月末存款 = 1000/(1 + 0.0171 / 12)
第46个月月末存款 = (第47个月月末存款 + 1000 )/(1 + 0.0171 / 12)
第45个月月末存款 = (第46个月月末存款 + 1000 )/(1 + 0.0171 / 12)
……
第1个月月末存款 = (第2个月月末存款 + 1000 )/(1 + 0.0171 / 12)
通过以上过程就可以逆推最初要存入多少钱。
网友评论