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

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

1 递归算法 Recursive Algorithm

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

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

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

if (条件)

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

else

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

如求阶乘的递归函数：

unsigned long factorial(unsigned long number)

{

if(number<=1);

reuturn 1;

else

return number*factorial(number-1);

}

必须有递归终止的条件 。

函数决定终止的参数有规律地递增或递减 。

在数据结构中，链表和二叉树都具备鲜明的递归特性。

2 递归消除

递归算法虽然强大，但是也不是万能的。从本质上来看，递归其实是方便了程序员却难为了机器。使用递归算法，只要得到递归数学公式就能方便地写出程序，程序可读性强，容易理解。但递归是用堆栈机制实现的，每深入一层递归，都要在内在中占去一块栈数据区域，这样一旦递归嵌套层数较深，计算机会力不从心，在空间上甚至会以内存崩溃而告终。即使能够完成递归计算，也会占据大量的内存空间，额外消耗大量的函数传递和函数调用资源。因此，也有一些消除递归的方法：

2.1 利用栈结构消除递归

利用一个栈来人工模拟系统堆栈的 操作过程。这种方法通用性强，但是本质上还是递归的，区别是将计算机做的事情改由人工来完成，因此对算法的优化效果不明显。

2.2 尾递归消除法

尾递归是一种特殊的递归方式，它的递归调用语句只有一个，并且是放在最后。其效率与循环的代码的执行效率基本上是相当的。其优化主要是对栈内空间的优化，这个优化是O(n)到O(1)的；至于时间的优化，其实是由于对空间的优化导致内存分配的工作减少所产生的，不会带来质的飞跃。

2.3 迭代法 Iterative Method

迭代算法迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程。主要是利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一些新值。

利用迭代算法解决问题，需要做好以下三方面的工作：

• 确定迭代变量；
• 建立迭代关系式
• 对迭代过程进行控制。

递归用的是选择结构，迭代则是采用循环结构：

unsigned long factorial(unsigned long number)

{

unsigned long result = 1;

for(unsigned long i = number; i>=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 <= 0) return n;

for ( i = 2; i<=n; ++i)

{ fn = fn_1 + fn_2;

fn_2 = fn_1; fn_1 = fn; }

return fn;

}

从上面的例子可以看出，迭代比较晦涩，如果使用递归方法能够更自然地反映问题，并且能够使程序易于理解和调试，那么就可以考虑使用递归而不是迭代。

对递归函数的每次调用都需要内存空间。由于很多调用的活动都是同时进行的，操作系统可能会耗尽可用的内存，所以应尽量避免过深的递归调用而产生溢出问题。