预计阅读本页时间：-
C允许一个函数调用其本身。这种调用过程被称作递归（recursion）。递归有时很难处理，而有时却很方便实用。当一个函数调用自己时，如果编程中没有设定可以终止递归的条件检测，它会无限制地进行递归调用，所以需要进行谨慎处理。
递归一般可以代替循环语句使用。有些情况下使用循环语句比较好，而有些时候使用递归更有效。递归方法虽然使程序结构优美，但其执行效率却没有循环语句高。
广告：个人专属 VPN，独立 IP，无限流量，多机房切换，还可以屏蔽广告和恶意软件，每月最低仅 5 美元
9.3.1 递归的使用
为了具体说明，请看下面的例子。程序清单9.6中函数main（）调用了函数up_and_down（）。我们把这次调用称为“第1级递归”。然后up_and_down（）调用其本身，这次调用叫做“第2级递归”。第2级递归调用第3级递归，依此类推。本例中共有4级递归。为了深入其中看看究竟发生了什么，程序不仅显示出了变量n的值，还显示出了存储n的内存的地址&n（本章稍后部分将更全面讨论&运算符。printf（）函数使用％p说明符来指示地址）。
程序清单9.6 recur.c程序
输出如下：
我们来分析程序中递归的具体工作过程。首先main（）使用参数1调用了函数up_and_down（）。于是up_and_down（）中形式参量n的值为1，故打印语句#1输出了Level 1。然后，由于n的数值小于4，所以up_and_down（）（第1级）使用参数n+1即数值2调用了up_and_down（）（第2级）。这使得n在第2级调用中被赋值2，打印语句#1输出的是Level 2。与之类似，下面的两次调用分别打印出Level 3和Level 4。
当开始执行第4级调用时，n的值是4，因此if语句的条件不满足。这时不再继续调用up_and_down（）函数。第4级调用接着执行打印语句#2，即输出LEVEL 4，因为n的值是4。现在函数需要执行return语句，此时第4级调用结束，把控制返回给该函数的调用函数，也就是第3级调用函数。第3级调用函数中前一个执行过的语句是在if语句中进行第4级调用。因此，它开始继续执行其后续的代码，即执行打印语句#2，这将会输出LEVEL 3。当第3级调用结束后，第2级调用函数开始继续执行，即输出了LEVEL 2。依此类推。
注意，每一级的递归都使用它自己私有的变量n。你可以通过查看地址的值来得出这个结论（当然，不同的系统通常会以不同的格式显示不同的地址。关键点在于，调用时的Levell地址和返回时的Levell地址是相同的）。
如果您对此感到有些迷惑，可以假想进行了一系列函数调用，即使用funl（）调用fun2（）、fun2（）调用fun3（），fun3（）调用fun4（）。fun4（）执行完后，fun3（）会继续执行。而fun3（）执行完后，开始继续执行fun2（）。最后fun2（）返回到fun1（）中并执行后续代码。递归过程也是如此，只不过fun1（）、fun2（）、fun3（）和fun4（）是相同的函数。
9.3.2 递归的基本原理
刚接触递归可能会感到迷惑，下面将讲述几个基本要点以便于理解该过程。
第一，每一级的函数调用都有自己的变量。也就是说，第1级调用中的n不同于第2级调用中的n，因此程序创建了4个独立的变量，虽然每个变量的名字都是n，但是它们分别具有不同的值。当程序最终返回到对up_and_down（）的第1级调用时，原来的n仍具有其初始值1（请参见图9.4）。
图9.4 递归中的变量
第二，每一次函数调用都会有一次返回。当程序流执行到某一级递归的结尾处时，它会转移到前第1级递归继续执行。程序不能直接返回到main（）中的初始调用部分，而是通过递归的每一级逐步返回，即从up_and_down（）的某一级递归返回到调用它的那一级。
第三，递归函数中，位于递归调用前的语句和各级被
调函数具有相同的执行顺序。例如，在程序清单9.6中，打印语句#1位于递归调用语句之前。它按照递归调用的顺序被执行了4次，即依次为第1级、第2级、第3级和第4级。
第四，递归函数中，位于递归调用后的语句的执行顺序和各个被调函数的顺序相反。例如，打印语句#2位于递归调用语句之后，其执行顺序是：第4级、第3级、第2级和第1级。递归调用的这种特性在解决涉及反向顺序的编程问题时很有用。下文中将给出这样的一个例子。
第五，虽然每一级递归都有自己的变量，但是函数代码并不会得到复制。函数代码是一系列的计算机指令，而函数调用就是从头执行这个指令集的一条命令。一个递归调用会使程序从头执行相应函数的指令集。除了为每次调用创建变量，递归调用非常类似于一个循环语句。实际上，递归有时可被用来代替循环，反之亦然。
最后，递归函数中必须包含可以终止递归调用的语句。通常情况下，递归函数会使用一个if条件语句或其他类似的语句以便当函数参数达到某个特定值时结束递归调用。比如在上例中，up_and_down（n）调用了up_and_down（n+1）。最后，实际参数的值达到4时，条件语句if（n<4）得不到满足，从而结束递归。
9.3.3 尾递归
最简单的递归形式是把递归调用语句放在函数结尾即恰在return语句之前。这种形式被称作尾递归（tail recursion）或结尾递归（end recursion），因为递归调用出现在函数尾部。由于尾递归的作用相当于一条循环语句，所以它是最简单的递归形式。
下面我们讲述分别使用循环和尾递归完成阶乘计算的例子。一个整数的阶乘就是从1到该数的乘积。例如，3的阶乘（写作3!）是1×2×3。0!等于1，而且负数没有阶乘。程序清单9.7中，第一个函数使用for循环计算阶乘，而第二个函数用的是递归方法。
程序清单9.7 factor.c程序
用来测试的驱动程序把输入限制在整数0到12之间。因为12!稍大于5亿，而13!比我们的系统中的long类型数据大得多，所以如果计算大于13!的阶乘，就必须使用范围更大的数据类型，比如double类型或long long类型。
下面是一个运行示例：
使用循环方法的函数把ans初始化为1，然后将其依次和从n到2依次递减的整数相乘。根据公式，ans还应该和1相乘，但这并不会改变结果。
下面我们研究使用递归方法的函数。其中关键的一点是n!=n×（n-1）!。因为（n-1）!是1到n-1的所有正数之积，所以该数乘以n就是n的阶乘。这也暗示了可以采用递归的方法。调用函数rfact（）时，rfact（n）就等于n×rfact（n-1）。这样就可以通过调用rfact（n-1）来计算rfact（n），如程序清单9.7中所示。当然，递归必须在某个地方结束，可以在n为0时把返回值设为1，从而达到结束递归的目的。
在程序清单9.7中，两个函数的输出结果相同。虽然对rfact（）的递归调用不是函数中的最后一行，但它是在n>0的情况下执行的最后一条语句，因此这也属于尾递归。
既然循环和递归都可以用来实现函数，那么究竟选择哪一个呢？一般来讲，选择循环更好一些。首先，因为每次递归调用都拥有自己的变量集合，所以就需要占用较多的内存；每次递归调用需要把新的变量集合存储在堆栈中。其次，由于进行每次函数调用需要花费一定的时间，所以递归的执行速度较慢。既然如此，那么我们为什么还要讲述以上例子呢？因为尾递归是最简单的递归形式，比较容易理解；而且在某些情况下，我们不能使用简单的循环语句代替递归，所以就有必要学习递归的方法。
9.3.4 递归和反向计算
下面我们考虑一个使用递归处理反序的问题（在这类问题中使用递归比使用循环更简单）。问题是这样的：编写一个函数将一个整数转换成二进制形式。二进制形式的意思是指数值以2为底数进行表示。例如234在十进制下表示为2×102+3×101+4×100，而二进制数101意思是1×22+0×21+1×20。二进制数只使用数字0和1表示。
解决上述问题，需要使用一个算法（algorithm）。例如，怎样得到5的二进制数表示？因为奇数的二进制形式的最后一位一定是1，而偶数的二进制数的最后一位是0，所以可以通过计算5%2得出5的二进制形式中最后一位数字是1或者0。一般来讲，对于数值n，其二进制数的最后一位是n%2，因此计算出的第一个数字恰是需要输出的最后一位数字。这就需要使用一个递归函数实现。在函数中，首先在递归调用之前计算n%2的数值，然后在递归调用语句之后进行输出。这样，计算出的第一个数值反而在最后一个输出。
为了得出下一个数字，需要把原数值除以2。这种计算就相当于在十进制下把小数点左移一位。如果此时得出的数值是偶数，则下一个二进制位的数值是0；若得出的数值为奇数，则下一个二进制位的数值就是1。例如，5/2的数值是2（整数除法），所以下一位值是0。这时已经得到了数值01。重复上述计算，即使用2除以2得出1，而1%2的数值是1，因此下一位值是1。这时得到的数值是101。那么何时停止这种计算呢？因为只要被2除的结果等于或大于2，那么就还需要一位二进制位进行表示，所以只有被2除的结果小于2时才停止计算。每次除以2就可以得出一位二进制位值，直到计算出最后一位为止（如果读者对此感到不解，可以在十进制下做类似的运算。628除以10的余数是8，因此8就是最后一位。上步计算的商是62，而62除以10的余数是2，所以2就是下一位值，依此类推）。在程序清单9.8中实现了上述算法。
程序清单9.8 binary.c程序
以上程序中，如果r是0，表达式‘0’+r就是字符‘0’；当r为1时，则该表达式的值为字符‘1’。得出这种结果的前提假设是字符‘1’的数值编码比字符‘0’的数值编码大1。ASCII和EBCDIC两种编码都满足上述条件。更一般的方式，你可以使用如下方法：
下面是一个简单的运行示例：
当然，不使用递归也能实现这个算法。但是由于本算法先计算出最后一位数值，所以在显示结果之前必须对所有的数值进行存储（比如放在一个数组之中）。第15章“位操作”给出了不用递归实现这个算法的例子。
9.3.5 递归的优缺点
使用递归既有优点也有缺点。其优点在于为某些编程问题提供了最简单的解决方法，而缺点是一些递归算法会很快耗尽计算机的内存资源。同时，使用递归的程序难于阅读和维护。从下面的例子中可以看出使用递归的优缺点。
斐波纳契数列定义如下：第一个和第二个数字都是1，而后续的每个数字是其前两个数字之和。例如，数列中前几个数字是1、1、2、3、5、8和13。斐波纳契数列在数学上很受重视，甚至有专门的刊物讨论它。本书不对此做深层次的探讨。下面我们创建一个函数，它接受一个正整数n作为参数，返回相应的斐波纳契数值。
首先，关于递归深度，递归提供了一个简单的定义。如果调用函数Fibonacci（），当n为1或2时Fibonacci（n）应返回1；对于其他数值应返回Fibonacci（n-1）+Fibonacci（n-2）：
这个C递归函数只是重述了递归的数学定义（为使问题简化，函数不处理小于1的数值）。同时本函数使用了双重递归（double recursion）；也就是说，函数对本身进行了两次调用。这就会导致一个弱点。
为了具体说明这个弱点，先假设调用函数Fibonacci（40）。第1级递归会创建变量n。接着它两次调用Fibonacci（），在第2级递归中又会创建两个变量n。上述的两次调用中的每一次又进行了两次调用，因而在第3级调用中需要4个变量n，这时变量总数为7。因为每级调用需要的变量数是上一级变量数的2倍，所以变量的个数是以指数规律增长的！正如第5章“运算符、表达式和语句”中的小麦粒数的例子，按指数规律增长会很快产生很大的数值。这种情况下，指数增长的变量数会占用大量内存，这就可能导致程序瘫痪。
当然，以上是一个比较极端的例子，但它也表明了必须小心使用递归，尤其是当效率处在第一位的时候。
