下载掌阅APP，畅读海量书库
立即打开
在解决许多数学问题中，根据已知条件，利用计算公式进行若干步重复的运算即可求解答案，这种方法被称为递推算法。根据推导问题的方向，可将递推算法分为顺推法和逆推法。
相对于递归算法，递推算法免除了数据进出栈的过程，也就是说，不需要函数不断地向边界值靠拢，而直接从边界出发，直到求出函数值。例如，阶乘函数： f （ n ）= n × f （ n -1）。
在 f （3）的运算过程中，递归的数据流动过程如下：
f(3){f(i)=f(i-1) * i}--＞f(2)--＞f(1)--＞f(0){f(0)=1}--＞f(1)--＞f(2)--f(3){f(3)=6}
而递推如下：
f(0)--＞f(1)--＞f(2)--＞f(3)
由此可见，递推的效率要高一些，在可能的情况下应尽量使用递推。但是递归作为比较基础的算法，它的作用不能忽视。所以，在把握这两种算法的时候应该特别注意。
【例3-2】 钓鱼比赛：6位同学钓鱼比赛，他们钓到的鱼数量都不相同。问第1位同学钓了多少条时，他指着旁边的第2位同学说比他多钓了2条，追问第2位同学，他说比第3位同学多钓了2条；如此，都说比另一位同学多钓了2条；最后问到第6位同学时，他说自己钓了3条。问第一位同学共钓鱼多少条？
'''递推算法'''
k=3
for i in range(1,6):
k+=2
print(k)
'''递归如下'''
def fish(n):
if n==6:
return 3
else:
return fish(n+1)+2
print(fish(1))
所谓顺推法是从已知条件出发，逐步推算出要解决的问题的方法叫顺推。斐波那契数列、汉诺塔问题是经典的顺推法。
1）斐波那契数列
斐波那契数列指的是这样一个数列：
1，1，2，3，5，8，13，21，34，55，89，144，233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368，…
这个数列从第3项开始，每一项都等于前两项之和。设它的函数为 f （ n ），已知 f （1）=1， f （2）=1， f （ n ）= f （ n -2）+ f （ n -1）（ n ＞=3， n ∈ N ），则通过顺推可以知道， f （3）= f （1）+ f （2）=2， f （4）= f （2）+ f （3）=3……直至得到要求的解。
【例3-3】 利用顺推法求解斐波那契数列。
2）汉诺塔问题
汉诺塔（又称河内塔）问题源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
【例3-4】 利用顺推法求解汉诺塔问题。
def move(n,a,b,c):
if n==1:
print(a,'--＞',c)
else:
move(n-1,a,c,b)
move(1,a,b,c)
move(n-1,b,a,c)
move(3,'a','b','c')
运行程序，输出如下：
a--＞c
a--＞b
c--＞b
a--＞c
b--＞a
b--＞c
a--＞c
逆推法从已知问题的结果出发，用迭代表达式逐步推算出问题的开始条件，即顺推法的逆过程。