2.2.1 递归值函数：n的阶乘（2）
来调用函数。图2-2描述了该调用所需的计算顺序。
这个函数符合本章前面介绍的递归解决方案模型：
1. fact的一个操作是调用自身。
2. 每递归调用fact一次，需要计算阶乘的整数减1。
3. 该函数对0的阶乘的处理与所有其他阶乘不同：它不生成递归调用。我们已经知道fact(0)的值为1。因此，当n为0时，出现基例。
4. 只要n是非负整数，第2条可确保一定能到达基例。
注释：fact函数满足递归解决方案的4个标准
提示：递归算法必须有基例，基例的解决方案不需要任何递归调用就可以直接知道。如果没有基例，递归函数将生成无限的调用序列。
函数fact要求的前置条件是n为非负整数。当递归调用fact(n-1)的时候，由于n是正数，因此n-1是非负整数。由于递归调用满足fact的前置条件，因此fact(n-1)就可以返回n-1的阶乘。这样，n*fact(n-1)是n的阶乘。第5章将使用数学归纳法正式证明fact(n)返回n的阶乘。
如果违背了fact的前置条件，则函数的行为将变得不正确。也就是说，如果调用程序传递了一个负数给fact，那么将导致无限的递归调用(只有在系统定义的限制下才会终止)，因为这个函数永远无法到达基例。例如，fact(-4)调用fact(-5), fact(-5)调用fact(-6)，依此类推。
注释：违背fact的前置条件会导致无限递归
理想情况下，这个函数应该保护自身不被负数干扰。例如，如果n<0，那么函数可以返回0或者设置错误标记。附录B在B.2节和B.5节讨论错误检测；到那时可以回顾此处的内容。
显然，fact函数实现了factorial的递归定义。现在分析执行递归函数的机制。除else子句中的表达式外，fact的逻辑简洁明了。这个表达式可以这样解释：
1. 计算n*fact(n-1)乘积的各个操作数。
2. 第二个操作数fact(n-1)是对函数fact的调用。虽然这是一个递归调用(fact调用fact)，但本身无任何特别之处。将fact的递归调用与调用另一个函数(如标准函数abs)对比可以发现，其原理是相同的：只是计算函数的值。
从理论上讲，递归函数求值并不比非递归函数求值复杂。然而实际上，手工记录的方式很快就会失去控制。下一部分内容将系统介绍跟踪递归函数动作的方法。对于计算机而言，记录非常简单，但是需要使用比分配给任务更多的内存。
问题1 下面的函数计算1到n(n>=1)的和，试说明这个函数是如何满足递归函数的标准的。
- /** Computes the sum of the integers from 1 through n.
- @pre n > 0.
- @post None.
- @param n A positive integer.
- @return The sum 1 + 2 + . . . + n. */
- int sumUpTo(int n)
- {
- int sum = 0;
- if (n == 1)
- sum = 1;
- else // n > 1
- sum = n + sumUpTo(n-1);
- return sum;
- } // end sumUpTo