递推算法是找出问题本身所具有的一种递推关系，然后进行求解的算法。递推时问题分解成若干步骤，找出相邻步骤之间的关系，从而计算出最后的解。

设要求解的问题规模为n，不断缩小规模直至n=1或0时，解或为已知。这种问题可以采用递推法算法，根据问题的递推性质，从规模为1或0时已知解，递推出规模为2，3，…，n-1的一系列解，最后求出问题规模为n的解。这样，程序就可以从i=0或i=1出发，重复地通过递推获得规模为i+1的解，最终得到规模为n的解。

通常，使用递推能够实现的算法，也可以使用递归算法来完成。

【例9-4】使用递推方法，求1！+2！+3！+…+10！。

程序思路：当规模为1时，1！=1为已知解，由此递推出2！=2×1！，3！=3×2！，……最终得出规模为n时的解n！=n×（n-1）！。例5-19同本题，该程序使用了两层循环来完成计算，每次计算i！都要从i=1开始。由于i！=i*（i-1）！，可以使用递推的方法，从题中多项式的前一项递推出后一项多项式。使用递推方法，只需要一层的循环就可以完成计算，大大地提高了程序的运行效率。

程序运行结果：

【例9-5】使用递推方法求出自然数e，要求精确到小数点后10位。其中e=1/1！+1/2！+1/3！+…+1/n！。

程序思路：与前一题相同，第i项与第i-1项的关系为i！=i*（i-1）！，所以，题中多项式的后一项可以由前一项递推而来。要求e的值精确到小数点后10位，应该使用while循环来实现，当最后一项1/n！＜10^-10时，结束计算。

程序运行结果：

e=2.7182818271175897

以上递推的方法是从已知条件出发逐步推算出要解决的问题。这种方法叫顺推方法。还有一种称为逆推的方法，就是从已知问题的结果出发，逐步推算出问题的开始的条件。逆推法是顺推法的逆过程。(www.daowen.com)

【例9-6】一只猴子采了一堆桃子，每天吃掉桃子的一半，又再吃一个。第7天吃完桃子就没了。编写程序计算这堆桃子原来有几个。

程序思路：这道题目与前面题目不同的是，前面题目从规模1递推到规模n，而本题只知道最后的规模是第7天的桃子数为2，吃完一半加1个时，桃子数为0。所以本题的递推方法是从规模n（第7天），逆推到规模1（第1天），最后求出第1天的桃子数。递推其递推关系为x1=（x2+1）*2，即前一天的桃子数是后一天的桃子数加1后的2倍。

程序运行结果：

第7天桃子数：2

第6天桃子数：6

第5天桃子数：14

第4天桃子数：30

第3天桃子数：62

第2天桃子数：126

第1天桃子数：254