Question

递归转非递归的五条规则

Answer 1

问：递归转非递归的五条规则

答：转化的方法一般有以下两种，一是递归转化为递推，用迭代的思想去求解，程序效率要高得多，如求Fabonacci数列问题；二是自己定义堆栈来模拟递归的过程，但会减低程序的可读性，如汉诺塔问题。第一种方法比较简单，下面重点讲一下第二种方法。设P是一个递归算法，假定P中共有m个值参和局部变量，共有t处递归调用P的语句，则把P改写成一个非递归算法的一般规则为：1、 定义一个栈S，用来保存每次递归调用前值参和局部变量的当前值以及调用后的返回地址。即S应该含有m+1个域，且S的深度必须足够大，使得递归过程中不会发生栈溢出。2、 定义t+2个语句标号，其中用一个标号标在原算法中的第一条语句上，用另一个标号标在作返回处理的第一条语句上，其余t个标号标在t处递归调用的返回地址，分别标在相应的语句上。3、 把每一个递归调用语句改写成如下形式：（1） 把值参和局部变量的当前值以及调用后的返回地址压入栈；

答：（2） 把值参所对应的实在参数表达式的值赋给值参变量；（3） 无条件转向原算法的第一条语句；4、 在算法结束前增加返回处理，当栈非空时做：（1） 出栈；（2） 把原栈顶中前m个域的值分别赋给各对应的值参和局部变量；（3） 无条件转向由本次返回地址所指定的位置；5、 增设一个同栈S的元素类型相同的变量，作为进出栈的缓冲变量，对于递归函数，还需要再增设一个保存函数值中间结果的临时变量，用这个变量替换函数体中的所有函数名，待函数结束之前，在把这个变量的值赋给函数名返回。6、 在原算法的第一条语句之前，增加一条把栈置空的语句。7、 对于递归函数而言，若某条赋值语句中包含两处或多处递归调用（假设为n处），则应首先把它拆成n条赋值语句，使得每条赋值语句只包含一处递归调用，同时对增加的n-1条赋值语句，要增设n-1个局部变量，然后按以上六条规则转换成非递归函数。