3.3.2 消除递归

用递归编制的算法具有结构清晰、易读，容易实现并且递归算法的正确性很容易得到证明。但是，递归算法的执行效率比较低，因为递归需要反复入栈，时间和空间开销大。

递归的算法也完全可以转换为非递归实现，这就是递归的消除。消除递归的方法有两种：一种是对于简单的递归可以直接利用迭代，通过循环结构就可以消除；另一种方法是利用栈的方式实现。例如，n的阶乘就是一个简单的递归，可以直接利用迭代就可以消除递归。n的阶乘的非递归算法如下。

n的阶乘的递归算法也可以转换为利用栈实现的非递归算法。当n=3时，递归调用过程如图3.17所示。

递归函数调用，参数进栈情况如图3.18所示。当n=1时，递归调用开始逐层返回，参数出栈情况如图3.19所示。在图中，为了叙述方便，用f代表fact函数。

利用栈模拟递归过程可以通过以下步骤实现：

（1）设置一个工作栈，用于保存递归工作记录，包括实在参数、返回地址等。

（2）将调用函数传递过来的参数和返回地址入栈。

（3）利用循环模拟递归分解过程，逐层将递归过程的参数和返回地址入栈。当满足递归结束条件时，依次逐层出栈，并将结果返回给上一层，直到栈空为止。

【例3.3】 编写求n!的递归算法与利用栈实现的非递归算法。

【分析】通过利用栈模拟在n的阶乘递归实现中，递归过程中的工作记录的进栈过程与出栈过程，实现非递归算法的实现。定义一个二维数组，数组的第一维用于存放本层参数n，第二维用于存放本层要返回的结果。

程序运行结果如图3.20所示。

思考题：利用栈，试着将n阶汉诺塔的递归转换为非递归算法。