【技术贴】递推、递归算法与数组的区别与联系

     2021-01-20           浏览数:

一、递推算法

1、递推算法所谓递推,是指从已知的初始条件出发,依据某种递推关系,逐次推出所要求的各中间结果及最后结果。其中初始条件或是问题本身已经给定,或是通过对问题的分析与化简后确定。

从已知条件出发逐步推到问题结果,此种方法叫顺推。

从问题出发逐步推到已知条件,此种方法叫逆推。

无论顺推还是逆推,其关键是要找到递推式。这种处理问题的方法能使复杂运算化为若干步重复的简单运算,充分发挥出计算机擅长于重复处理的特点。

递推法是一种重要的数学方法,在数学的各个领域中都有广泛的运用,也是计算机用于数值计算的一个重要算法。

递推算法的首要问题是得到相邻的数据项间的关系(即递推关系)。递推算法避开了求通项公式的麻烦,把一个复杂的问题的求解,分解成了连续的若干步简单运算。一般说来,可以将递推算法看成是一种特殊的迭代算法。

2、递推算法是一种理性思维模式的代表,其根据已有的数据和关系,逐步推导而得到结果。递推算法的

执行过程如下:

(1)根据已知结果和关系,求解中间结果。

(2)判定是否达到要求,如果没有达到,则继续根据已知结果和关系求解中间结果。如果满足要求,则表示寻找到一个正确的答案。

二、递归算法

递归算法是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数(或过程)来表示问题的解。一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数)。

递归过程一般通过函数或子过程来实现。递归方法:在函数或子过程的内部,直接或者间接地调用自己的算法。

递归算法是一种直接或者间接地调用自身算法的过程。在计算机编写程序中,递归算法对解决一大类问题是十分有效的,它往往使算法的描述简洁而且易于理解。

递归算法解决问题的特点:

(1) 递归就是在过程或函数里调用自身。

(2) 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口。

(3) 递归算法解题通常显得很简洁,但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。

(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。

递归算法所体现的“重复”一般有三个要求:

一是每次调用在规模上都有所缩小(通常是减半);

二是相邻两次重复之间有紧密的联系,前一次要为后一次做准备(通常前一次的输出就作为后一次的输入);

三是在问题的规模极小时必须用直接给出解答而不再进行递归调用,因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件),无条件递归调用将会成为死循环而不能正常结束。

20170615220708910.png

三、递推与递归的区别

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

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

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

顺推法

所谓顺推法是从已知条件出发,逐步推算出要解决的问题的方法叫顺推。

如斐波拉契数列,设它的函数为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……直至我们要求的解。

逆推法

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

四、递归与循环的区别

英文的Recursion从词源上分析只是"re-  (again)" + "curs- (come, happen)" 也就是重复发生,再次重现的意思。 而对应的中文翻译 ”递归“ 却表达了两个意思:”递“+”归“。 这两个意思,正是递归思想的精华所在。从这层次上来看,中文翻译反而更达意。跟循环的区别单看上面的定义,貌似跟通常所说的无限死循环很像,他们的区别在哪?

递归是静中有动,有去有回。

循环是动静如一,有去无回。

举个例子,给你一把钥匙,你站在门前面,问你用这把钥匙能打开几扇门。

递归:你打开面前这扇门,看到屋里面还有一扇门(这门可能跟前面打开的门一样大小(静),也可能门小了些(动)),你走过去,发现手中的钥匙还可以打开它,你推开门,发现里面还有一扇门,你继续打开,。。。, 若干次之后,你打开面前一扇门,发现只有一间屋子,没有门了。 你开始原路返回,每走回一间屋子,你数一次,走到入口的时候,你可以回答出你到底用这钥匙开了几扇门。

循环:你打开面前这扇门,看到屋里面还有一扇门,(这门可能跟前面打开的门一样大小(静),也可能门小了些(动)),你走过去,发现手中的钥匙还可以打开它,你推开门,发现里面还有一扇门,(前面门如果一样,这门也是一样,第二扇门如果相比第一扇门变小了,这扇门也比第二扇门变小了(动静如一,要么没有变化,要么同样的变化)),你继续打开这扇门,。。。,一直这样走下去。 入口处的人始终等不到你回去告诉他答案。

3. 递归思想递归就是有去(递去)有回(归来)。具体来说,为什么可以”有去“? 这要求递归的问题需要是可以用同样的解题思路来回答类似但略有不同的问题(上面例子中的那一把钥匙可以开后面门上的锁)。为什么可以”有回“?这要求这些问题不断从大到小,从近及远的过程中,会有一个终点,一个临界点,一个baseline,一个你到了那个点就不用再往更小,更远的地方走下去的点,然后从那个点开始,原路返回到原点。

递归与循环是两种不同的解决问题的典型思路。递归通常很直白地描述了一个问题的求解过程,因此也是最容易被想到解决方式。循环其实和递归具有相同的特性,即做重复任务,但有时使用循环的算法并不会那么清晰地描述解决问题步骤。单从算法设计上看,递归和循环并无优劣之别。然而,在实际开发中,因为函数调用的开销,递归常常会带来性能问题,特别是在求解规模不确定的情况下;而循环因为没有函数调用开销,所以效率会比递归高。递归求解方式和循环求解方式往往可以互换,也就是说,如果用到递归的地方可以很方便使用循环替换,而不影响程序的阅读,那么替换成循环往往是好的。问题的递归实现转换成非递归实现一般需要两步工作:

   (1)、 建立“堆栈(一些局部变量)”来保存这些内容以便代替系统栈,比如树的三种非递归遍历方式;

   (2)、 把对递归的调用转变为对循环处理。

沁中NOIP.gif