C语言实现递归的基本原理

开始之前，首先来看一个通常我们不会以递归的形式思考的问题。假设我们想计算整数n的阶乘。n的阶乘可写作n!，其结果是1~n之间的各数之积。比如，4！=4×3×2×1。一种计算法方法是循环遍历其中的每一个数，然后与它之前的数相乘作为结果再参与下一次计算。这种方法称为迭代法，可以正式定义为：

n! = (n)(n - 1)(n - 2) . . . (1)

看待这个问题的另一种方式是将n!定义为更小的阶乘形式。为了实现这一步，我们将n!定义为n-1阶乘的n倍。当然，求解（n-1）!的过程同n!一样，只是变小了一些。如果我们再把（n-1）!看做n-1倍的（n-2）!，（n-2）!看做n-2倍的（n-3）!，一直到n=1时，我们就计算完了。这就是递归的方式，可以正式定义为：

图3-1展示了利用递归的方法计算的4!过程。它也勾画出了递归过程中的两个基本阶段：递推与回归。在递推阶段，每一个递归调用通过进一步调用自己来记住这次递归过程。当其中有调用满足终止条件时，递推结束。比如，在计算n的阶乘时，终止条件是当n=1和n=0，此时函数只须简单地返回1即可。每一个递归函数都必须拥有至少一个终止条件；否则，递推阶段就永远不会结束了。一旦递推阶段结束，处理过程就进入回归阶段，在这之前的函数调用以逆序的方式回归，直到最初调用的函数返回为止，此时递归过程结束。

Figure 3.1. Computing 4! recursively

示例3-1展示了一个C函数fact，它接受一个整数n作为参数，以递归的方式计算n的阶乘。该函数按照如下的方式工作：如果n小于0，该函数直接返回0，这代表一个错误。如果n等于0或者1，该函数返回1，这是因为o!和1!都等于1，以上就是终止递归的条件。否则，函数返回n-1的阶乘的n倍。而n-1的阶乘又会以递归的方式再次调用fact来计算，如此继续。注意观察递归实现与我们之前对递归的定义之间的相同点。

Example 3.1. Implementation of a Function for Computing Factorials Recursively

int fact(int n) {
if (n < 0)
   return 0;
else if (n == 0)
   return 1;
else if (n == 1)
   return 1;
else
   return n * fact(n - 1);
}

为了理解递归究竟是如何工作的，有必要先看看C语言中函数的执行方式。基于这点，我们需要了解一点关于C程序在内存中的组织方式。基本上来说一个可执行程序由4个区域组成：代码段、静态数据区、堆与栈（见图3-2a）。代码段包含程序运行时所执行的机器指令。静态数据区包含在程序生命周期内一直持久的数据，比如全局变量和静态局部变量。堆包含程序运行时动态分配的存储空间，比如用malloc分配的内存。栈包含函数调用的信息。按照惯例，堆的增长方向为从程序低地址到高地址向上增长，而栈的增长方向刚好相反（实际情况可能不是这样，与CPU的体系结构有关）。

当C程序中调用了一个函数时，栈中会分配一块空间来保存与这个调用相关的信息。每一个调用都被当做是活跃的。栈上的那块存储空间称为活跃记录，或者称为栈帧。栈帧由5个区域组成：输入参数、返回值空间、计算表达式时用到的临时存储空间、函数调用时保存的状态信息以及输出参数（见图3-2b）。输入参数是传递到活跃记录中的参数；输出参数是传递给在活跃记录中调用的函数所使用的。一个活跃记录中的输出参数就成为栈中下一个活跃记录的输入参数。函数调用产生的活跃记录将一直存在于栈中直到这个函数调用结束。

回到示例3-1，考虑一下当计算4!时栈中都发生了些什么。初始调用fact会在栈中产生一个活跃记录，输入参数n=4（见图3-3，第1步）。由于这个调用没有满足函数的终止条件，因此fact将继续以n=3为参数递归调用。这将在栈上创建另一个活跃记录，但这次输入参数（见图3-3，第2步）。这里，n=3也是第一个活跃期中的输出参数，因为正是在第一个活跃期内调用fact产生了第二个活跃期。这个过程将一直继续，直到n的值变为1，此时满足终止条件，fact将返回1（见图3-3，第4步）。

Figure 3.2. The organization in memory of (a) a C program and (b) an activation record

Figure 3.3. The stack of a C program while computing 4! recursively

一旦当n=1时的活跃期结束，n=2时的递归计算结果就是2×1=2，因而n=2时的活跃期也将结束，返回值为2（见图3-3，第5步）。结果就是n=3时的递归计算结果表示为3×2=6，因此n=3时的活跃期结束，返回值为6（见图3-3，第6步）。最终，当n=4时的递归计算结果将表示为6×4=24，n=4时的活跃期将结束，返回值为24（见图3-3，第7步）。此时，函数已经从最初的调用中返回，递归过程结束。

栈是用来存储函数调用信息的绝好方案，这正是由于其后进先出的特点（见第6章）精确满足了函数调用和返回的顺序。然而，使用栈也有一些缺点。栈维护了每个函数调用的信息直到函数返回后才释放，这需要占用相当大的空间，尤其是在程序中使用了许多递归调用的情况下。除此之外，因为有大量的信息需要保存和恢复，因此生成和销毁活跃记录需要耗费一定的时间。如此一来当函数调用的开销变得很大时，我们就需要考虑应该采用迭代的方案。幸运的是，我们可以采用一种称为尾递归的特殊递归方式来避免前面提到的这些缺点。