经典算法|递归和递归消除的迭代法

关注
经典算法|递归和递归消除的迭代法www.shan-machinery.com

任何一个可以用计算机解决的问题所需的计算时间都与其规模有关系,这也就意味着,通常情况下问题规模越大,所耗费的时间和计算资源越多;而问题的规模越小,所需的时间和计算资源越小,问题的求解也越容易,因此,在处理一些困难问题的时候,我们会考虑通过缩小问题的规模而使得困难问题更加容易求解。在充分研究这类算法的规律之后,人们将这些算法总结成缩小规模算法,如递归法、分治法、动态规划法、贪心法等。

1 递归算法 Recursive Algorithm

递归算法,简而言之就是一种函数调用函数自身来完成算法设计的方法。是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数(或过程)来表示问题的解。

递归这种函数实际上只知道如何解决最简单的情况,或者所谓的基本情况。如果函数为解决基本情况而调用,那么它将简单地返回一个结果。如果函数为解决较复杂的问题而调用,那么它通常会把问题分成两个概念性的部分:一部分是函数知道如何去做的,另一部分是函数不知道如何去做的。为了使递归可行,后一部分必须和原来的问题相类似,但是相对稍微简单一些或者稍微小一些。这个新问题看起来和原来的问题颇为相似,因为函数启动(调用)自己的一个全新副本用于解决这一问题-这就是递归调用,也称为递归步骤。递归步骤通常包括关键字return,因为它的结果会与函数知道如何解决问题的一部分结合起来,从而形成可传递回原来的调用者-可能就是main函数的结果。

 

递归的标准模式(有可对函数的入口进行测试的基本情况)

if (条件)

return (不需要递归的简单答案);

else

return (递归调用同一函数);

如求阶乘的递归函数:

unsigned long factorial(unsigned long number)

{

if(number=1; i--)

result *= i;

return result;

}

对于大多数常用的递归都有简单、等价的迭代程序。究竟使用哪一种,凭你的经验选择。

迭代程序复杂,但效率高。

递归程序逻辑清晰,但往往效率较低(空间复杂度高)。

3 迭代和递归对比

迭代和递归都是基于控制语句的:迭代使用循环结构,递归使用选择结构。

迭代和递归都涉及到循环,迭代显式地使用循环结构,递归通过重复的函数调用实现循环。

迭代和递归均包括终止条件测试,迭代在循环继续条件失败时终止,递归在达到基本情况时终止。计数器控制的循环和迭代和递归都是逐步达到终止的。迭代修改计数器直到计数器的值使循环条件不满足;递归产生比原来的问题简单的版本直到达到基本情况。

递归有许多不足之处。它不断地进行函数调用,必然会增加很多开销。这样不仅消耗处理器的时间,还会消耗内存空间。每个递归调用都会创建函数的一份副本(实际上只是函数中的变量),这也会占用相当可观的内存。而迭代器通常发生在一个函数内,因此没有重复的函数调用的开销和额外的内存分配。

4 Fibonacci函数的递归和迭代实现

可以用递归解决的问题绝大部分都可以用迭代(非递归)解决。

Fibonacci函数的递归实现

int f(int n)

{if (n==0) return 0;

elseif (n==1) return 1;.

else return (f(n-1)+f(n-2));

}

经典算法|递归和递归消除的迭代法

Fibonacci函数的迭代实现

int f(int n)

{ int i, fn, fn_1 = 0, fn_2 = 1;

if (n https://www.shan-machinery.com