3.2用递归计算阶乘
阶乘（factorial）是基斯顿·卡曼于1808年发明的运算符号。阶乘也是数学里的一种术语，在很多计算中都要使用到阶乘。
3.2.1 阶乘该怎么计算
一个正整数的阶乘是所有小于或等于该数的正整数的积，并且有0的阶乘为1的约定。自然数n的阶乘写作n!。
例如，求5的阶乘的算式如下：
从上式可看出，当求n的阶乘时，就从1逐项相乘到n即可，这是一个循环结构，因此编写一个循环程序就可很容易地求出数据n的阶乘，在第1章中曾给出过一个通过循环计算阶乘的C语言程序。
由于阶乘的结果会呈几何级数增长，在32位计算机中，只能计算到13的阶乘，14的阶乘结果就超过32位二进制的表示。即使是在64位字长的计算机中，能表示的数据大小也是有限的，只能保存20的阶乘。
如果需要求很大的数的阶乘（例如求1000的阶乘），就不能简单地使用第1章中介绍的阶乘程序来进行运算了。
如何超越计算机变量的取值范围来计算阶乘？这就需要考虑编写出能处理大整数的函数（在C# 4中已要提供了大整数功能），才能计算更大数的阶乘。由于篇幅所限，这里不单独编写大整数的函数，而是提供另外一种相对简单的求大数阶乘的方法。
这种思路就是：考虑将多位数相乘化解为一位数相乘，例如，11的阶乘为39916800，若需要求12的阶乘，则需要将39916800与12相乘，按手工计算乘法的竖式方法，可用2与39916800相乘的结果加上用1与39916800相乘的结果，然后再将结果相加，得到12的阶乘，如图3-6左图所示。由于前一数的阶乘的结果很大，按左图的方式计算也很容易导致溢出。根据乘法交换律，可以将左图所示算式转换为右图所示算式，这样，每次计算的结果就不容易出现溢出。
图3-6 乘法竖式
按图3-6所示的思路，定义一个数组，使数组的每一个数组元素保存阶乘的一位结果（如图3-6右图所示中，11的阶乘结果为8位，就用数组中的8个数组元素分别保存这8位）。当要计算12的阶乘时，可按以下步骤进行计算。
（1）用12去乘以数组中的每个元素，并将结果保存到原来的数组元素中。
（2）判断每个数组元素中的值是否大于9，若大于9则进行进位操作。通过进位操作，使数组中每个元素保存的值都只有一位数。
具体操作过程如图3-7所示。
图3-7
通过这种方式，就可以计算出计算机整型变量所能表示数据的十分之一这么大的数的阶乘了（因为数组中保存的是0～9中的1位数，而为了使结果不超过整型变量表示范围，与数组中各元素相乘的数据只能是计算机整型变量所能表示数据的十分之一）。
按这种思路，编写能计算较大整数阶乘的程序，具体代码如下：
执行以上程序计算1000的阶乘，可得到如图3-8所示的结果。从结果中可看到，1000的阶乘共有2568位。
图3-8
3.2.2 阶乘的递归计算方法
从前面的运算过程可看出，阶乘是一个规模比较大的问题，这时可考虑通过递归的方式来计算阶乘。
在定义递归算法时，需要考虑3个方面的问题。
首先，每一次递归调用，处理问题的规模应有所缩小，在阶乘中可以做到，如求n的阶乘，可将其分解为如下形式：
由上式可看到，n的阶乘可分解为n乘以（n－1）的阶乘，而（n－1）的阶乘又可分解为（n－1）与（n－2）的阶乘。
这样，每次运算就可将问题的规模缩小。
其次，在定义递归算法时，相邻两次递归调用之间有紧密的联系，前一次为后一次递归调用做准备。在上式中可看到，n的阶乘分解后，下一次递归调用时的输入就为（n－1）。
最后，在问题的规模极小时，必须直接给出解答而不再进行递归调用。在阶乘的递归算法中，计算到最后，求0的阶乘时，就不用再递归，直接返回其结果为1即可。
根据上面的分析，可用以下方式定义阶乘的递归算法。
根据以上定义，可用C语言编写出如下递归计算阶乘的程序。
可以看出，这个程序比第1章中编写的阶乘程序简单。
3.2.3 递归的过程
要理解递归，首先应了解一种数据结构：堆栈（简称栈）的概念。
栈是一个后进先出的压入（push）和弹出（pop）式数据结构。在程序运行时，系统每次向栈中压入一个对象，然后栈指针向上移动一个位置。当系统从栈中弹出一个对象时，最近进栈的对象将被弹出，然后栈指针向下移动一个位置。
C编译器处理函数调用时，就是使用栈来保存数据的。当主调函数调用另一个函数时，C编译器将主调函数的所有实参和返回地址压入到栈中，栈指针将移到合适的位置来容纳这些数据。
当进行被调函数时，编译器将栈中的实参数据弹出，赋值给函数的形参。在被调用函数执行期间，还可利用栈来保存函数执行时的局部变量。当被调用函数准备返回时，系统将弹出栈中所有当前函数压入栈中的值，这时，栈指针移动到被调用函数刚开始执行时的位置。接着被调用函数返回，系统从栈中弹出返回地址，主调函数就可以继续执行了。
如图3-9所示就是计算机中栈的示例，左图所示是“函数1”调用“函数2”的情况，在调用“函数2”时，计算机将“函数2”的返回地址压入栈中，接着将函数参数压入栈中。而右图显示“函数2”调用结束返回“函数1”后的情况，这时“函数2”中的参数、返回地址都从栈中弹出。
图3-9
栈在每个程序中都是存在的，它不需要程序员编写代码去维护，而是由系统自动处理。
递归之所以能实现，是因为函数的每个执行过程都在栈中有自己的形参和局部变量的备份，这些备份和函数的其他执行过程毫不相干。这种机制是大多数程序设计语言实现子程序结构的基础，使得递归成为可能。
假定某个主调函数调用了一个被调用函数，再假定被调用函数又反过来调用了主调用函数。这第二个调用就被称为调用函数的递归，因为它发生在调用函数的当前执行过程运行完毕之前。而且，因为这个原先的主调用函数、现在的被调用函数在栈中处于较低的位置，有它独立的一组参数和自变量，原先的参数和变量将不受影响，所以递归能正常工作。
书归正传，回到阶乘的递归算法上来。假设要计算5的阶乘，通过前面设计的递归程序执行过程如下。
首先，在main()函数中调用fact()函数，将返回地址、参数、局部变量压入堆栈，如图3-10所示。
图3-10
在fact()函数中，判断n的值若不为0，则递归调用fact(4)，这时将函数的返回地址和参数压入堆栈，如图3-11所示。
图3-11
将程序继续递归调用时，将fact(3)、fact(2)、fact(1)逐步压入堆栈，如图3-12所示为将fact(0)压入堆栈后栈的结构。
图3-12
当调用fact(0)时，达到阶乘递归算法的结束条件，这时结束fact(0)函数调用，从堆栈中弹出该层的相关数据，并返回函数的结果1。这时栈顶中保存的将是fact(1)中的相关数据，如图3-13所示。
图3-13
当递归函数逐层返回时，栈中压入的数据将逐步弹出，当弹出fact(4)后的栈结果如图3-14所示。
图3-14
当函数fact(5)返回时得到5的阶乘等于120，同时从栈中弹出调用函数时的数据，完成整个递归调用。
3.2.4 递归的本质：缩小问题规模
递归式解决逻辑问题的基本思想是：把规模大的、较难解决的问题变成规模较小的、易解决的同一问题。规模较小的问题又变成规模更小的问题，并且小到一定程度可以直接得出它的解，从而得到原来问题的解。
用递归处理问题的过程，就是将问题规模逐步缩小的过程。
例如，在阶乘的递归运算中，就是将一个较大数的阶乘逐步缩小为一个较小数的阶乘，直到缩小到求0的阶乘为止。
在上节的例子中，用递归求解最大公约数的方法也同样如此，利用辗转相除法，在递归调用过程中逐步将被除数、除数缩小。
因此，在解决问题时，如果可以明确地将求解问题规则逐步缩小，就可考虑用递归算法来实现。
利用递归算法编写的程序代码更简洁清晰，可读性更好。有的算法用递归表示比用循环表示简洁精练，而且某些问题，特别是与人工智能有关的问题，更适宜用递归方法，如八皇后问题、汉诺塔问题等。有的算法用递归能实现，而用循环却不一定能实现。
但是，也需要注意递归算法一个明显的缺点，每次递归调用时，需要将返回地址、参数等数据压入堆栈，也就是说，递归的内部实现要消耗额外的空间和时间。如果递归调用的层次太深，就可能导致堆栈溢出，从而使程序执行出错。