9.3 递归
C允许函数调用它自己，这种调用过程称为递归（recursion）。递归有时难以捉摸，有时却很方便实用。结束递归是使用递归的难点，
因为如果递归代码中没有终止递归的条件测试部分，一个调用自己的函数会无限递归。
可以使用循环的地方都可以使用递归。有时用循环解决问题比较好，但有时用递归更好。递归方法更简洁，但效率却没有循环高。
9.3.1 演示递归
main()函数调用up_and_down()函数，这次调用称为“第1级递归”。然后up_and_down()调用自己，这次调用称为“第2级递归”。接着
第2级递归调用第3级递归，一次类推。
%p转换说明打印地址，如果你的系统不支持这种该是，请使用%u或%lu代替%p）。
/* recur.c -- recursion illustration */
#include <stdio.h>
void up_and_down(int);
int main(void)
{
up_and_down(1);
return 0;
}
void up_and_down(int n)
{
printf("Level %d: n location %p\n", n, &n); // 1
if (n < 4)
up_and_down(n+1);
printf("LEVEL %d: n location %p\n", n, &n); // 2
}
/* 输出：
*/
注意，每级递归的变量n都属于本级递归私有。这从程序输出的地址值可以看出（当然，不同的系统表示的地址格式不同，这里关键要注意，Level 1和LEVEL 1的地址相同，Level 2和LEVEL 2的地址相同，等等）。
如果觉得不好理解，可以假设有一条函数调用链---fun1()调用fun2()、fun2()调用fun3()、fun3()调用fun4()。当fun4()调用结束后，控制传回fun3()；当fun3()调用结束后，控制传回fun2()；当fun2()调用结束后，控制传回fun1()；递归的情况与此类似，只不过fun1()、fun2()、fun3()、fun4()都是相同的函数。
9.3.2 递归的基本原理
第1，每级递归都有自己的变量。
第2，每次函数调用都会返回一次。但函数执行完毕后，控制权将被传回上一级递归。程序必须按顺序逐级返回递归。
第3，递归函数中位于递归之前的语句，均按被调用函数的顺序执行。
第4，递归函数中位于递归之后的语句，均按被调用函数相反的顺序执行。递归调用的这种特性在解决设计相反顺序的编程问题时很有用。
第5，虽然每级递归都有自己的变量，但是并没有拷贝函数的代码。程序按顺序执行函数中的代码，而递归调用就相当于又从头开始执行函数的代码。除了为每次递归调用创建变量外，递归调用非常类似于一个循环语句。实际上，递归有时候可用循环来代替，循环有时也能用递归来代替。
第6，递归函数必须包含能让递归调用停止的语句。通过，递归函数都使用if或其他等价的测试条件在函数参数等于某特定值时终止递归。为此，每次递归调用的形式都要使用不同的值。
9.3.3 尾递归
最简单的递归形式是把递归调用置于函数的末尾，即正好在return语句之前。这种形式的递归被称为尾递归（tail recursion），因为递归调用在函数的末尾。尾递归是最简单的递归形式，因为它相当于循环。
循环和尾递归计算阶乘。一个正整数的阶乘（factorial）是从1到该整数的所有整数的乘积。另外0!等于1，负数没有阶乘。
// factor.c -- uses loops and recursion to calculate factorials
#include <stdio.h>
long fact(int n);
long rfact(int n);
int main(void)
{
int num;
printf("This program calculates factorials.\n");
printf("Enter a value in the range 0-12 (q to quit):\n");
while (scanf("%d", &num) == 1)
{
if (num < 0)
printf("No negative numbers, please.\n");
else if (num > 12)
printf("Keep input under 13.\n");
else
{
printf("loop: %d factorial = %ld\n",
num, fact(num));
printf("recursion: %d factorial = %ld\n",
num, rfact(num));
}
printf("Enter a value in the range 0-12 (q to quit):\n");
}
printf("Bye.\n");
return 0;
}
long fact(int n) // loop-based function
{
long ans;
for (ans = 1; n > 1; n--)
ans *= n;
return ans;
}
long rfact(int n) // recursive version
{
long ans;
if (n > 0)
ans= n * rfact(n-1);
else
ans = 1;
return ans;
}
/* 输出：
*/
输入限制在0~12。因为12!已快接近5亿，而13!比62亿还大，已超过我们系统中long类型能表示的返回。要计算超过12的阶乘，必须使用能表示更大范围的类型，如double或long long。
使用循环将ans初始化为1，然后把ans与n~2的所递减整数相乘。根据阶乘的公式，还应该乘以1，但是这并不会改变结果。
阶乘递归函数的关键是n! = n * (n - 1)!。可以这样做是因为(n-1)!是n-1~1的所有正整数的乘积。因此，n乘以n-1的阶乘就得到n的阶乘。阶乘的这一特性很适合时使用递归。当然，必须要在满足条件时结束递归，可以在n等于0时把返回值设为1。
注意，虽然rfact()的递归调用不是函数的最后一行，但是当n>0时，它是该函数执行的最后一条语句，因此它也是尾递归。
既然用递归和循环来计算都没有问题，那么一般应该使用哪一个？一般而言，选择循环比较好。首先，每次递归都会创建一组变量，所以递归使用的内存更多，而且每次递归调用都会把创建的一组新变量防止栈中。递归调用的数量受限于内存空间。其次，由于每次函数调用要花费一定的时间，所以递归的执行速度较慢。演示这个程序示例的目的是什么？因为尾递归是递归中最简单的形式，比较容易理解。在某些情况下，不能用简单的循环代替递归，因此读者还是要好好理解递归。
9.3.4 递归和倒序计算
递归在处理倒序时非常方便（在解决这类问题中，递归比循环简单）。
打印一个整数的二进制数。二进制表示法根据2的幂来表示数字。二进制由0和1表示。
设计一个以二进制形式表示整数的方法或算符（algorithm）。例如，如何用二进制表示十进制5？在二进制中，奇数的末尾一定是1，偶数的末尾一定是0，所以通过5%2即可确定5的二进制数的最后一位是1还是0。一般而言，对于数字n，其二进制的最后一位是n%2。因此，计算的第1位数字实际上是待输出二进制数的最后一位。这一规律提示我们，在递归函数的递归调用之前计算n%2，在递归调用之后打印计算结果。这样，计算的第1个值正好是最后一个打印的值。
要获得下一位数字，必须把原数除以2。这种计算方法相当于在十进制下把小数点左移一位，如果计算结果是偶数，那么二进制的下一位数就是0；如果是奇数，就是1。程序何时停止呢？当与2相除的结果小于2时停止计算，因为只要结果大于或等于2，就说明还有二进制位。
/* binary.c -- prints integer in binary form */
#include <stdio.h>
void to_binary(unsigned long n);
int main(void)
{
unsigned long number;
printf("Enter an integer (q to quit):\n");
while (scanf("%lu", &number) == 1)
{
printf("Binary equivalent: ");
to_binary(number);
putchar('\n');
printf("Enter an integer (q to quit):\n");
}
printf("Done.\n");
return 0;
}
void to_binary(unsigned long n) /* recursive function */
{
int r;
r = n % 2;
if (n >= 2)
to_binary(n / 2);
putchar(r == 0 ? '0' : '1');
return;
}
/* 输出：
*/
不用递归也能实现用二进制形式表示整数的算法。但是由于这种算法要首先存储最后一位二进制数，所以在显示结果之前必须把所有的位数都存储在别处（例如，数组）。第15章会介绍不用递归实现该算法的例子。
9.3.5 递归的优缺点
优点是递归为某些编程问题提供了最简单的解决方案。缺点是一些递归算法会快速消耗计算机的内存资源。另外，递归不方便阅读和维护。
斐波那契数列的定义如下：第1个和第2个数字都是1，而后续的每个数字都是前两个数字之和。
递归实现的版本：
unsigned long Fibonacci( unsigned n ){
if( n > 2 ){
return Fibonacci( n - 1 ) + Fibonacci( n - 2 );
} else{
return 1;
}
}
这个递归函数只是重述了数学定义的递归。该函数使用了双递归（double recursion），即函数每一级递归都要调用本身两次。这暴露了一个问题。
由于每级递归创建的变量都是上一级递归的两倍，所以变量的数量呈指数增长！指数增长很快就会产生非常大的值。指数增长的变量数量很快就消耗掉计算机的大量内存，很可能导致程序崩溃。
该例说明：在程序中使用递归要特别注意，尤其是效率优先的程序。
所有的C函数皆平等
程序中的每个C函数与其他函数都是平等的。每个函数都可以调用其他函数，或被其他函数调用。这点与Pascal中的过程不同，虽然过程可以嵌套在另一个过程中，但是嵌套在不同过程中的过程之间不能相互调用。
main()函数与其他函数不同。main()的确有点特殊。当main()与程序中的其他函数放在一起时，最开始执行的是main()函数中的第1条语句，但是这也是局限之处。main()也可以被自己或其他函数递归调用---尽管很少这样做。