肯尼斯·里科《C和指针》第7章 函数（2）递归

7.5 递归

C通过运行时堆栈支持递归函数的实现。递归函数就是直接或间接调用自身的函数。许多教科书都把计算阶乘和斐波那契数列用来说明递归，这是非常不幸的。在第1个例子中，递归并没有提供任何优越之处。在第2个例子中，它的效率之低是非常恐怖的。

这里有一个简单的程序，可用于说明递归。程序的目的是把一个整数从二进制形式转换为可打印的字符形式。例如，给出一个值4267，我们需要依次产生字符‘4’‘2’‘6’和‘7’。如果在printf函数中使用了%d格式码，它就会执行这类处理。

我们采用的策略是把这个值反复除以10，并打印各个余数。例如，4267除10的余数是7，但是不能直接打印这个余数。我们需要打印的是机器字符集中表示数字‘7’的值。在ASCII码中，字符‘7’的值是55，所以需要在余数上加上48来获得正确的字符。但是，使用字符常量而不是整型常量可以提高程序的可移植性。考虑下面的关系：

'0' + 0 = '0';
'0' + 1 = '1';
'0' + 2 = '2';

从这些关系中可以很容易看出在余数上加上‘0’就可以产生对应字符的代码。接着就打印出余数。下一步是取得商，4267/10等于426。然后用这个值重复上述步骤。

批注：这个小点可以记下。

这种处理方法存在的唯一问题是它产生的数字次序正好相反，它们是逆向打印的。程序7.6使用递归来修正这个问题。

程序7.6中的函数是递归性质的，因为它包含了一个对自身的调用。乍一看，函数似乎永远不会终止。当函数调用时，它将调用自身，第2次调用还将调用自身，以此类推，似乎会永远调用下去。但是，事实上这种情况并不会出现。

这个程序的递归实现了某种类型的螺旋状while循环。while循环在循环体每次执行时必须取得某种进展，逐步迫近循环终止条件。递归函数也是如此，它在每次递归调用后必须越来越接近某种限制条件。当递归函数符合这个限制条件时，它便不再调用自身。

在程序7.6中，递归函数的限制条件就是变量quotient为零。在每次递归调用之前，我们都把quotient除以10，所以每递归调用一次，它的值就越来越接近零。当它最终变成零时，递归便告终止。

/*
** 接受一个整型值（无符号），把它转换为字符并打印它。前导零被删除。
*/
#include <stdio.h>
void
binary_to_ascii( unsigned int value )
{
    unsigned int     quotient;
    quotient = value / 10;
    if( quotient != 0 )
         binary_to_ascii( quotient );
    putchar( value % 10 + '0' );
}

程序7.6 将二进制整数转换为字符 btoa.c

批注：其实就是不会进到if循环里吧。

一旦理解了递归，阅读递归函数最容易的方法不是纠缠于它的执行过程，而是相信递归函数会顺利完成它的任务。如果每个步骤正确无误，限制条件设置正确，并且每次调用之后更接近限制条件，递归函数总是能够正确地完成任务。

批注：数学归纳法hhh。

7.5.1 追踪递归函数

为了能理解递归的工作原理，需要追踪递归调用的执行过程，所以让我们来进行这项工作。追踪一个递归函数执行过程的关键是理解函数中所声明的变量是如何存储的。当函数被调用时，它的变量的空间是创建于运行时堆栈上的。以前调用的函数的变量仍保留在堆栈上，但它们被新函数的变量所掩盖，因此是不能被访问的。

当递归函数调用自身时，情况也是如此。每进行一次新的调用，都将创建一批变量，它们将掩盖递归函数前一次调用所创建的变量。在追踪一个递归函数的执行过程时，必须把分属不同次调用的变量区分开来，以避免混淆。

程序7.6的函数有两个变量：参数value和局部变量quotient。下面显示了堆栈的状态，当前可以访问的变量位于栈顶。所有其他调用的变量饰以灰色阴影，表示它们不能被当前正在执行的函数访问。

假定以4267这个值调用递归函数。当函数刚开始执行时，堆栈的内容如下图所示。

执行除法运算之后，堆栈的内容如下。

接着，if语句判断出quotient的值非零，所以对该函数执行递归调用。这个函数第二次被调用之初，堆栈的内容如下。

堆栈上创建了一批新的变量，隐藏了前面的那批变量，除非当前这次递归调用返回，否则它们是不能被访问的。再次执行除法运算之后，堆栈的内容如下。

quotient的值现在为42，仍然非零，所以需要继续执行递归调用，并再创建一批变量。在执行完这次调用的除法运算之后，堆栈的内容如下。

此时，quotient的值还是非零，仍然需要执行递归调用。在执行除法运算之后，堆栈的内容如下。

不算递归调用语句本身，到目前为止所执行的语句只是除法运算以及对quotient的值进行测试。由于递归调用使这些语句重复执行，因此它的效果类似循环：当quotient的值非零时，把它的值作为初始值重新开始循环。但是，递归调用将会保存一些信息（这一点与循环不同），也就是保存在堆栈中的变量值。这些信息很快就会变得非常重要。

现在quotient的值变成了零，递归函数便不再调用自身，而是开始打印输出。然后函数返回，并开始销毁堆栈上的变量值。每次调用putchar得到变量value的最后一个数字，方法是对value进行模10取余运算，其结果是一个0～9之间的整数。把它与字符常量‘0’相加，其结果便是对应于这个数字的ASCII字符，然后把这个字符打印出来。

接着函数返回，它的变量从堆栈中销毁。接着，递归函数的前一次调用重新继续执行，它所使用的是自己的变量，它们现在位于堆栈的顶部。因为它的value值是42，所以调用putchar后打印出来的数字是2。

接着递归函数的这次调用也返回，它的变量也被销毁，此时位于堆栈顶部的是递归函数再前一次调用的变量。递归调用从这个位置继续执行，这次打印的数字是6。在这次调用返回之前，堆栈的内容如下。

现在我们已经展开了整个递归过程，并回到该函数最初的调用。这次调用打印出数字7，也就是它的value参数除10的余数。

然后，这个递归函数就彻底返回到其他函数调用它的地点。

如果把打印出来的字符一个接一个排在一起，将其显示在打印机或屏幕上，将看到正确的值：4267。

批注：期末考试就考了一道这样的题，但我这个蒟蒻当然没有做出来，如果考前看到这个就好了，唉，，，

7.5.2 递归与迭代

递归是一种强有力的技巧，和其他技巧一样，它也可能被误用。这里就有一个例子。阶乘的定义往往就是以递归的形式描述的，如下所示。

                ----→     n ≤ 0: 1
factorial(n) =
                ----→     n > 0: n × factorial(n – 1)

这个定义同时具备了我们开始讨论递归所需要的两个特性：存在限制条件，当符合这个条件时递归便不再继续；每次递归调用之后越来越接近这个限制条件。

用这种方式定义阶乘往往引导人们使用递归来实现阶乘函数，如程序7.7a所示。这个函数能够产生正确的结果，但它并不是递归的良好用法。为什么？递归函数调用将涉及一些运行时开销——参数必须压到堆栈中、为局部变量分配内存空间（所有递归均如此，并非特指这个例子）、寄存器的值必须保存等。当递归函数的每次调用返回时，上述这些操作必须还原，恢复成原来的样子。所以，基于这些开销，对于这个程序而言，它并没有简化问题的解决方案。

批注：唉，我们上课就没讲过这些。

/*
** 用递归方法计算n的阶乘。
*/
long
factorial( int n )
{
       if( n <= 0 )
           return 1;
       else
           return n * factorial( n - 1 );
}

程序7.7a 递归计算阶乘 fact_rec.c

程序7.7b使用循环计算相同的结果。尽管这个使用简单循环的程序不甚符合前面阶乘的数学定义，但它却能更为有效地计算出相同的结果。如果仔细观察递归函数，就会发现递归调用是函数所执行的最后一项任务。这个函数是尾部递归(tail recursion)的一个例子。由于函数在递归调用返回之后不再执行任何任务，因此尾部递归可以很方便地转换成一个简单循环，完成相同的任务。

*
** 用迭代方法计算n的阶乘。
*/
long
factorial( int n )
{
       int      result = 1;
       while( n > 1 ){
            result *= n;
            n -= 1;
       }
       return result;
}

程序7.7b 迭代计算阶乘 fact_itr.c

许多问题是以递归的形式进行解释的，这只是因为它比非递归形式更为清晰。但是，这些问题的迭代实现往往比递归实现效率更高，虽然代码的可读性可能稍差一些。当一个问题相当复杂，难以用迭代形式实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开销。