22-递归的优缺点

9.3.5　递归的优缺点

递归既有优点也有缺点。优点是递归为某些编程问题提供了最简单的解决方案。缺点是一些递归算法会快速消耗计算机的内存资源。另外，递归不方便阅读和维护。我们用一个例子来说明递归的优缺点。

斐波那契数列的定义如下：第1个和第2个数字都是 1 ，而后续的每个数字都是其前两个数字之和。例如，该数列的前几个数是： 1 、 1 、 2 、 3 、 5 、 8 、 13 。斐波那契数列在数学界深受喜爱，甚至有专门研究它的刊物。不过，这不在本书的讨论范围之内。下面，我们要创建一个函数，接受正整数 n ，返回相应的斐波那契数值。

首先，来看递归。递归提供一个简单的定义。如果把函数命名为 Fibonacci() ，那么如果 n 是 1 或 2 ， Fibonacci(n) 应返回 1 ；对于其他数值，则应返回 Fibonacci(n-1)+Fibonacci(n-2) ：

unsigned long Fibonacci(unsigned n)
{
     if (n > 2)
          return Fibonacci(n-1) + Fibonacci(n-2);
     else
          return 1;
}

这个递归函数只是重述了数学定义的递归。该函数使用了双递归（double recursion），即函数每一级递归都要调用本身两次。这暴露了一个问题。

为了说明这个问题，假设调用 Fibonacci(40) 。这是第1级递归调用，将创建一个变量 n 。然后在该函数中要调用 Fibonacci() 两次，在第2级递归中要分别创建两个变量 n 。这两次调用中的每次调用又会进行两次调用，因而在第3级递归中要创建4个名为 n 的变量。此时总共创建了7个变量。由于每级递归创建的变量都是上一级递归的两倍，所以变量的数量呈指数增长！在第5章中介绍过一个计算小麦粒数的例子，按指数增长很快就会产生非常大的值。在本例中，指数增长的变量数量很快就消耗掉计算机的大量内存，很可能导致程序崩溃。

虽然这是个极端的例子，但是该例说明：在程序中使用递归要特别注意，尤其是效率优先的程序。

所有的C函数皆平等

程序中的每个C函数与其他函数都是平等的。每个函数都可以调用其他函数，或被其他函数调用。这点与Pascal和Modula-2中的过程不同，虽然过程可以嵌套在另一个过程中，但是嵌套在不同过程中的过程之间不能相互调用。

main ()函数是否与其他函数不同？是的， main ()的确有点特殊。当 main ()与程序中的其他函数放在一起时，最开始执行的是 main ()函数中的第1条语句，但是这也是局限之处。 main ()也可以被自己或其他函数递归调用—尽管很少这样做。