20-尾递归

9.3.3　尾递归

最简单的递归形式是把递归调用置于函数的末尾，即正好在 return 语句之前。这种形式的递归被称为尾递归（tail recursion），因为递归调用在函数的末尾。尾递归是最简单的递归形式，因为它相当于循环。

下面要介绍的程序示例中，分别用循环和尾递归计算阶乘。一个正整数的阶乘（factorial）是从1到该整数的所有整数的乘积。例如，3的阶乘（写作3！）是1×2×3。另外，0！等于1，负数没有阶乘。程序清单9.7中，第1个函数使用 for 循环计算阶乘，第2个函数使用递归计算阶乘。

程序清单9.7　 factor.c 程序

// factor.c -- 使用循环和递归计算阶乘
#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)     // 使用循环的函数
{
     long ans;
     for (ans = 1; n > 1; n--)
          ans *= n;
     return ans;
}
long rfact(int n)    // 使用递归的函数
{
     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 。

下面是该程序的运行示例：

This program calculates factorials.
Enter a value in the range 0-12 (q to quit):
5
loop: 5 factorial = 120
recursion: 5 factorial = 120
Enter a value in the range 0-12 (q to quit):
10
loop: 10 factorial = 3628800
recursion: 10 factorial = 3628800
Enter a value in the range 0-12 (q to quit):
q
Bye.

使用循环的函数把 ans 初始化为 1 ，然后把 ans 与从 n~2 的所有递减整数相乘。根据阶乘的公式，还应该乘以 1 ，但是这并不会改变结果。

现在考虑使用递归的函数。该函数的关键是 n! = n × (n-1)! 。可以这样做是因为 (n-1)! 是 n-1~1 的所有正整数的乘积。因此， n 乘以 n-1 的阶乘就得到 n 的阶乘。阶乘的这一特性很适合使用递归。如果调用函数 rfact() ， rfact(n) 是 n * rfact(n-1) 。因此，通过调用 rfact(n-1) 来计算 rfact(n) ，如程序清单9.7中所示。当然，必须要在满足某条件时结束递归，可以在 n 等于 0 时把返回值设为 1 。

程序清单9.7中使用递归的输出和使用循环的输出相同。注意，虽然 rfact() 的递归调用不是函数的最后一行，但是当 n>0 时，它是该函数执行的最后一条语句，因此它也是尾递归。

既然用递归和循环来计算都没问题，那么到底应该使用哪一个？一般而言，选择循环比较好。首先，每次递归都会创建一组变量，所以递归使用的内存更多，而且每次递归调用都会把创建的一组新变量放在栈中。递归调用的数量受限于内存空间。其次，由于每次函数调用要花费一定的时间，所以递归的执行速度较慢。那么，演示这个程序示例的目的是什么？因为尾递归是递归中最简单的形式，比较容易理解。在某些情况下，不能用简单的循环代替递归，因此读者还是要好好理解递归。