3.12 递归

前面介绍的程序通常由严格按层次方式调用的函数组成。对有些问题，可以用自己调用自己的函数。递归函数(recursive function)是直接调用自己或通过另一函数间接调用自己的函数。递归是个重要问题，在高级计算机科学教程中都会详细介绍。本节和下节介绍一些简单递归例子，本书则包含大量递归处理。图3.17(3．14节末尾)总结了本书的递归例子和练习。

我们先介绍递归概念，然后再介绍几个包含递归函数的程序。递归问题的解决方法有许多相同之处。调用递归函数解决问题时，函数实际上只知道如何解决最简单的情况(称为基本情况)。对基本情况的函数调用只是简单地返回一个结果。如果在更复杂的问题中调用函数，则函数将问题分成两个概念性部分：函数中能够处理的部分和函数中不能够处理的部分。

为了进行递归，后者要模拟原问题，但稍作简化或缩小。由于这个新问题与原问题相似，因此函数启动(调用)自己的最新副本来处理这个较小的问题，称为递归调用(reeursive call)或递归步骤(reeursive step)。递归步聚还包括关键字return，因为其结果与函数中需要处理的部分组合，形成的结果返回原调用者(可能是main)。递归步骤在原函数调用仍然打开时执行，即原调用还没有完成。

递归步骤可能导致更多递归调用，因为函数-继续把函数调用的新的子问题分解为两个概念性部分。要让递归最终停止，每次函数调用时都使问题进一步简化，从而产生越来越小的问题．最终合并到基本情况。这时，函数能识别并处理这个基本情况，并向前一个函数副本返回结果，并回溯一系列结果，直到原函数调用最终把最后结果返回给main。这一切比起前面介绍的其他问题似乎相当复杂．下面通过一个例子来说明。我们用递归程序进行一个著名的数学计算。

非负整数n的阶乘写成n!,为下列数的积：

n*(n—1)·(n—2)*...*l

其中1，等于1, 0定义为1。例如，51为5*4*3*2*1．即120。
整数number大于或等于0时的阶乘可以用下列for循环迭代(非递归)计算：

factorial = l；
for { int counter = number；counter >= 1；counter-- )
factorial *= counter；

通过下列关系可以得到阶乘函数的递归定义：

n!=n*(n-1)!

例如，5!等于5*4!，如下所示：

5!＝5*4*3*2*l
5!=5*(4*3*2*1)
5!=5*(4!)

求值5!的过程如图3.13。图3.13 a)显示如何递归调用，直到1!求值为1，递归终止。图3.13 b)显示每次递归调用向调用者返回的值，直到计算和返回最后值。

// Fig. 3.14:fig03 14.cpp
// Recursive factorial function
#include <iostream.h>
#include <iomanip,h>
unsigned long factorial(unsigned long);
int main()
{
  for (iht i = O; i <= 10 : i++)
    cout << setw(2) << 1 << "! = " << factorial(i) << endl;
  return 0;
}
// Recursive definition of function factorial
unsigned long factorial(unsigned long number)
{
  if (number <= 1) // base case
    return 1;
  else // recursive case
    return number * factorial(number - 1);
}

输出结果：

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10!= 3628800

图3.14的程序用递归法计算并打印。到10的整数阶乘(稍后将介绍数据类型unsigned long的选择)。递归函数factorial首先测试终止条件是否为true，即number是否小于或等于1。如果number小于或等于1，则factorial返回1，不再继续递归，程序终止。如果number大于1，则下列语句。

return number  *factorial( number - 1 )；

将问题表示为number乘以递归调用dactorial求值的number-1的阶乘。注意factorial(number-1)比原先factorial(number)的计算稍微简单一些。