【算法 - 方法】(1)递推

【算法 - 方法】(1)递推

递推法

递推是按照一定的规律来计算序列中的每个项,通常是通过计算前面的一些项来得出序列中的指定项的值。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复,该算法利用了计算机速度快和不知疲倦的机器特点。

递推算法是一种简单的算法,即通过已知条件,利用特定关系得出中间推论,直至得到结果的算法。递推算法分为顺推和逆推两种。

1.递推概念

给定一个数的序列H0,H1,…,Hn,…若存在整数n0,使当n>n0时,可以用等号(或大于号、小于号)将Hn与其前面的某些项Hi(0<i<n)联系起来,这样的式子就叫做递推关系。

递推是从已有(已知)的数据(初时条件)出发,根据某种递推关系,逐步推出中间结果,推出最后结果。

2.顺推

所谓顺推法是从已知条件出发,逐步推算出要解决的问题的方法叫顺推。
如斐波拉契数列,设它的函数为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.逆推

所谓逆推法从已知问题的结果出发,用迭代表达式逐步推算出问题的开始的条件,即顺推法的逆过程,称为逆推。

逆推则从已知到的结果出发,逐步推出问题的开始条件。

4.递推与递归比较

相对于递归算法,递推算法免除了数据进出栈的过程,也就是说,不需要函数不断的向边界值靠拢,而直接从边界出发,直到求出函数值.

比如阶乘函数: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)

由此可见,递推的效率要高一些,在可能的情况下应尽量使用递推.但是递归作为比较基础的算法,它的作用不能忽视.所以,在把握这两种算法的时候应该特别注意。

递推和递归很相似,一般他们两个可以相互转换。

使用递归时,如果递归深度太深可能会导致栈溢出问题。

参考

递推算法:https://baike.baidu.com/item/%E9%80%92%E6%8E%A8%E7%AE%97%E6%B3%95/2025952

算法--递推策略:https://www.cnblogs.com/wuyudong/p/4265019.html