《C和指针》笔记27：递归

递归所需要的两个特性：

1. 存在限制条件，当符合这个条件时递归便不再继续；
2. 每次递归调用之后越来越接近这个限制条件。

这里没有用计算阶乘和菲波那契数列的例子说明递归，作者指出前者递归并没有提供任何优越之处。而后者效率之低是非常恐怖的。

下面程序的目的是把一个整数转换为可打印的字符形式。

/*
** 接受一个整型值（无符号），把它转换为字符并打印它。前导零被删除。
*/
#include 
void
binary_to_ascii( unsigned int value )
{
	unsigned int quotient;
	quotient = value / 10;
	if( quotient != 0 )
		binary_to_ascii( quotient );
	putchar( value % 10 + '0' );
}
1
2
3
4
5
6
7
8
9
10
11
12
13

直接对10取余并循环打印会导致逆向打印，这里使用递归解决这个问题。在上面的程序中递归函数的限制条件就是变量quotient为零。在每次递归调用之前，我们都把quotient除以10，所以每递归调用一次，它的值就越来越接近零。当它最终变成零时，递归便告终止。

我们拆解上面的工作流程：

1．将参数值除以10。
2．如果quotient的值为非零，调用binary_to_ascii打印quotient当前值的各位数字。
3．接着，打印步骤1中除法运算的余数。

可能看了这个流程我们还是不理解递归是怎么运作的。一个递归函数执行过程的关键是理解函数中所声明的变量是如何存储的。当函数被调用时，它的变量的空间是创建于运行时堆栈上的。以前调用的函数的变量仍保留在堆栈上，但它们被新函数的变量所掩盖，因此是不能被访问的。

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

前面的程序有两个变量：参数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的余数。

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