3.2.4　栈与递归

栈的一个重要应用是在程序设计语言中实现递归过程。现实中，有许多实际问题是递归定义的，这时用递归方法可以使许多问题的结果大大简化。下面以n！为例。

n！的定义为：

根据定义可以写出相应的递归函数：

递归函数都有一个终止递归的条件，如上例n＝0时，将不再继续递归下去。

递归函数的调用类似于多层函数的嵌套调用，只是调用单位和被调用单位是同一个函数而已。在每次调用时系统将属于各个递归层次的信息组成一个活动记录（activation record），这个记录中包含着本层调用的实参、返回地址、局部变量等信息，并将这个活动记录保存在系统的“递归工作栈”中，每当递归调用一次，就要在栈顶为过程建立一个新的活动记录，一旦本次调用结束，则将栈顶活动记录出栈，根据获得的返回地址信息返回到本次的调用处。下面以求3！为例说明执行调用时工作栈中的状况。

为了方便将求阶乘程序修改如下。

算法3.7 求阶乘程序

函数调用过程如图3－9所示。其中R1为主函数调用fact（3）时返回点地址，R2为fact函数中递归调用fact（2）时返回点地址。

图3－9 递归工作栈示意

程序的执行过程可用图3－10来示意。

设主函数中n＝3：

图3－10 fact（3）的执行过程