2.2  返回值的递归

递归：镜子

当递归函数返回一个值而不只是执行动作的时候，递归的机制相当清楚，下面详细讲述这样一个函数。

2.2.1  递归值函数：n的阶乘（1）

计算整数n的阶乘是一个很好的示例，因为这个问题的递归方案易于理解，并且完全符合前面描述的模式。不过，该问题存在简洁高效的迭代解决方案，因此在实际中不应该用递归。

注释：如果某个问题具有更为高效简洁的解决方案，不要使用递归

首先来看为人熟知的factorial(n)(常写作n!)的迭代定义。

factorial(n) = n × (n-1) × (n-2) ×…×1   整数n > 0

factorial(0) = 1

注释：阶乘的迭代定义

负整数的阶乘未定义。根据上述定义，应能轻松地编写出迭代的阶乘函数。

为递归地定义factorial(n)，首先要根据更小整数的阶乘来定义factorial(n)。观察可知，n的阶乘等于n-1的阶乘乘以n。即：
 

注释：递归关系

factorial(n)是根据factorial(n-1)定义的，这是一种递归关系，意味着可通过factorial(n-2)来定义factorial(n-1)，依此类推。这个过程与词典查找解决方案类似，在词典例子中，也是按这种方式通过查找更小的词典解决问题的。

factorial(n)的定义缺少一个关键元素：基例。与词典查找解决方案一样，此处也必须定义一个不同于所有其他情况的实例，否则递归将无法结束。阶乘函数的基例是factorial(0)，其值为1。n的初值大于等于0，并且每次调用factorial时n将减1，这样就一定能到达基例。添加基例后，阶乘函数的完整递归定义为：
 

注释：阶乘的递归定义

为了理解此递归定义，将其用于计算factorial(4)。因为4>0，所以其递归定义描述为：

factorial(4) = 4 × factorial(3)

同理

factorial(3) = 3 × factorial(2)

factorial(2) = 2 × factorial(1)

factorial(1) = 1 × factorial(0)

这样就到达了基例。由阶乘定义，直接可知

factorial(0) = 1

递归定义的应用到此为止，但是您仍然不知道初始问题的答案：factorial(4)的值是多少？不过，现在已经有了回答该问题的信息：

因为factorial(0) = 1，所以factorial(1) = 1 × 1 = 1

因为factorial(1) = 1，所以factorial(2) = 2 × 1 = 2

因为factorial(2) = 2，所以factorial(3) = 3 × 2 = 6

因为factorial(3) = 6，所以factorial(4) = 4 × 6 = 24

可将递归看成这样一个过程：把问题分解成本人可完成的任务和朋友可代为完成的任务。例如，若要求计算factorial(4)，首先确定是否能直接得到答案。我们立刻可以想到factorial(0)=1，也就是说知道基例的值，但是无法立即知道factorial(4)的值。不过，如果朋友代您计算factorial(3)，则可通过4乘以factorial(3)来计算factorial(4)。这样，您的任务是计算乘积，而朋友的任务是计算factorial(3)。

现在，由朋友计算factorial(3)，所用过程与计算factorial(4)的过程相同。朋友确定factorial(3)不是基例，于是请另一位朋友计算factorial(2)。知道了factorial(2)，朋友就可计算factorial(3)；当您从朋友那儿了解到factorial(3)的值后，就可以计算factorial(4)。

注意，factorial(4)的递归定义得到的结果与迭代定义相同，即4×3×2×1=24。可以用数学归纳法证明，这两种factorial定义对所有非负整数都是一样的(见附录E)。第5章讨论递归与数学归纳法的紧密联系。

阶乘函数的递归定义说明了两点：①直观。可通过factorial(n-1)定义factorial(n)。②机械。可用该定义来确定给定阶乘的值。即使在这个简单例子中，应用递归定义也要做不少工作。当然，这些都是计算机来完成的。

一旦完成了对factorial(n)的递归定义，就很容易创建实现该定义的C++函数。
 

/** Computes the factorial of the nonnegative integer n.  
@pre  n must be greater than or equal to 0.  
@post  None.  
@return  The factorial of n; n is unchanged. */  
int fact(int n)  
{  
if (n == 0)  
return 1;  
else // n > 0, so n–1 >= 0. Thus, fact(n–1) returns (n–1)!  
return n * fact(n–1); // n * (n-1)! is n!  
} // end fact  

假设用语句
 

cout << fact(3);