【转】基本递归、尾递归(算法精解:C语言描述)

基本递归

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

1
n! = (n)(n - 1)(n - 2)(n - 3) ··· (1)

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

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

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

上图以递归方式计算阶乘的函数实现:

1
2
3
4
5
6
7
8
9
10
// 实例1
int fact(int n) {
if (n < 0)
return 0;
else if (n <= 1)
return 1;
else
return n * fact(n - 1);
}

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

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

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

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

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

尾递归

如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时,这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作,这个特性很重要,因为大多数现代的编译器会利用这种特点自动生成优化的代码。

当编译器检测到一个函数调用是尾递归的时候,它就覆盖当前的活跃记录而不是在栈中去创建一个新的。编译器可以做到这点,因为递归调用是当前活跃期内最后一条待执行的语句,于是当这个调用返回时栈帧中并没有其他事情可做,因此也就没有保存栈帧的必要了。通过覆盖当前的栈帧而不是在其之上重新添加一个,这样所使用的栈空间就大大缩减了,这使得实际的运行效率会变得更高。因此,只要有可能我们就需要将递归函数写成尾递归的形式。

为了理解尾递归是如何工作的,让我们再次以递归的形式计算阶乘。首先,这可以很容易让我们理解为什么之前所定义的递归不是尾递归。回忆之前对计算n!的定义:在每个活跃期计算n倍的(n-1)!的值,让n=n-1并持续这个过程直到n=1为止。这种定义不是尾递归的,因为每个活跃期的返回值都依赖于用n乘以下一个活跃期的返回值,因此每次调用产生的栈帧将不得不保存在栈上直到下一个子调用得不保存在栈上直到下一个子调用的返回值确定 。现在让我们考虑以尾递归的形式来定义计算n!的过程 。函数可以定义成如下形式 :

这种定义还需要接受第二个参数a,除此之外并没有太大区别。a(初始化为1)维护递归层次的深度。这就让我们避免了每次还需要将返回值再乘以n。然而,在每次递归调用中,令a=na并且n=n-1。继续递归调用,直到n=1,这满足结束条件,此时直接返回a即可。图6说明了用尾递归计算4!的过程。注意在回归的过程中不需要做任何操作,这是所有尾递归函数的标志。

代码实例2给出了一个C函数facttail,它接受一个整数n并以尾递归的形式计算n的阶乘。这个函数还接受一个参数a,a的初始值为1。facttail使用a来维护递归层次的深度,除此之外它和fact很相似。读者可以注意一下函数的具体实现和尾递归定义的相似之处。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 实例2
int facttail(int n, int a)
{
if (n < 0)
return 0;
else if (n == 0)
return 1;
else if (n == 1)
return a;
else
return facttail(n - 1, n * a);
}

示例2中的函数是尾递归的,因为对facttail的单次递归调用是函数返回前最后执行的一条语句。在facttail中碰巧最后一条语句也是对facttail的调用,但这并不是必需的。换句话说,在递归调用之后还可以有其他的语句执行,只是它们只能在递归调用没有执行时才可以执行。图7展示了当使用尾递归函数计算4!时栈使用的情况,读者可以和图5展示的栈使用情况做对比。