浅谈递归向非递归转换方法

⼀、什么是递归 很多数据结构的定义都是根据递归性质来进⾏定义的，是因为这些结构固有的性质。

递归是指某个函数直接或间接的调⽤⾃⾝。

问题的求解过程就是划分成许多相同性质的⼦问题的求解，⽽⼩问题的求解过程可以很容易的求出，这些⼦问题的解就构成⾥原问题的解了。

⼆、递归的⼏个特点 1.递归式，就是如何将原问题划分成⼦问题。

2.递归出⼝，递归终⽌的条件，即最⼩⼦问题的求解，可以允许多个出⼝。

3.界函数，问题规模变化的函数，它保证递归的规模向出⼝条件靠拢 三、递归的运做机制 很明显，很多问题本⾝固有的性质就决定此类问题是递归定义，所以递归程序很直接算法程序结构清晰、思路明了。

但是递归的执⾏过程却很让⼈费解，这也是让很多⼈难理解递归的原因之⼀。

由于递归调⽤是对函数⾃⾝的调⽤，在⼀次调⽤没有结束之前⼜开始了另外⼀次调⽤，按照作⽤域的规定，函数在执⾏终⽌之前是不能收回所占⽤的空间，必须保存下来，这也就意味着每⼀次的调⽤都要把分配的相应空间保存起来。

为了更好管理这些空间，系统内部设置⼀个栈，⽤于存放每次函数调⽤与返回所需的各种数据，其中主要包括函数的调⽤结束的返回地址，返回值，参数和局部变量等。

其过程⼤致如下： 1.计算当前函数的实参的值 2.分配空间，并将⾸地址压栈，保护现场 3.转到函数体，执⾏各语句，此前部分会重复发⽣(递归调⽤) 4.直到出⼝，从栈顶取出相应数据，包括，返回地址，返回值等等，收回空间，恢复现场，转到上⼀层的调⽤位置继续执⾏本次调⽤未完成的语句。

四、引⼊⾮递归 从⽤户使⽤⾓度来说，递归真的很简便，对程序宏观上容易理解。

递归程序的时间复杂度虽然可以根据T(n)=T(n-1)*f(n)递归求出，其中f(n)是递归式的执⾏时间复杂度，⼀般来说，时间复杂度和对应的⾮递归差不多，但是递归的效率是相当低的它主要发费在反复的进栈出栈，各种中断等机制上(具体的可以参考操作系统)更有甚者，在递归求解过程中，某些解会重复的求好⼏次，这是不能容忍的，这些也是引⼊⾮递归机制的原因之⼀。

递归问题的非递归实现方法的应用研究1.简单递归问题的非递归实现使用递归机制求解问题的算法程序，其前提是必须使用分划技术，把需要求解的问题分划成若干和原问题结构相同，但规模较小的子问题，使原问题的解建立在子问题解的基础上，而子问题的求解只需通过递归调用即可实现。

由于求解过程是从原问题开始，通过不断地递归调用，使原问题的解建立在子问题的解的基础上，子问题的解又建立在其他更小的子问题的基础上，知道可以直接求解的最小子问题为止。

递归的这种求解方式称为自顶向下产生计算序列，必然导致程序执行过程中许多重复的函数调用，这是导致递归程序执行效率降低的主要原因之一。

递推技术同样以分划技术为基础，与递归方式不同的是，递推方法是采用自底向上的方式产生计算序列，它首先计算规模最小的子问题的解，然后在此基础上依次计算规模较大子问题的解，直到最后产生的结果总是直接以前面已有的计算结果为基础，避免了许多重复的计算，因而递推方法产生的算法程序比递归算法具有更高的效率。

在对递归问题进行分析研究的过程中发现，有一类递归问题，使用非递归方法求解时可以直接求解，无需回溯，将该类递归问题称之为简单递归问题。

由于递归方法和递推方法在求解问题时均使用了分划技术，且递推的求解过程恰巧为递归求解过程的逆过程，因此完全可以使用递推方法求解简单递归问题，获得其高效的非递归算法程序。

其具体步骤如下：（1）把求解的问题分划成若干和原问题结构相同，但规模较小的子问题，并建立原问题与子问题解之间的递推关系。

（2）定义若干变量，用于记录递推关系中每个子问题的解。

（3）确定算法求解的初始状态和终止状态，分别作为循环的初始条件和结束条件，循环体部分即为根据（1）中确定的递推关系，不断修改步骤（2）中定义的变量的值，直至到达终止状态为止。

问题1：如果你的老师第一天给你一元钱，后面每一天给你的钱是前一天的2倍。

也即1,2,4,8，…，现问到了第n天时你的总收入是多少？该问题属于简单递归问题，其递归程序如下：int dayvalue (int day){if ( day==1) return (1);else return (2*dayvalue(day-1));}int totlevalue (int day){if (day==1) return (1);else return( dayvalue (day) + totlevalue(day-1))；}只要通过totlevalue（n）的执行即可获得上述问题的解。

递归算法向非递归算法转换递归算法向非递归算法转换递归算法实际上是一种分而治之的方法，它把复杂问题分解为简单问题来求解。

对于某些复杂问题(例如hanio塔问题)，递归算法是一种自然且合乎逻辑的解决问题的方式，但是递归算法的执行效率通常比较差。

因此，在求解某些问题时，常采用递归算法来分析问题，用非递归算法来求解问题；另外，有些程序设计语言不支持递归，这就需要把递归算法转换为非递归算法。

将递归算法转换为非递归算法有两种方法，一种是直接求值，不需要回溯；另一种是不能直接求值，需要回溯。

前者使用一些变量保存中间结果，称为直接转换法；后者使用栈保存中间结果，称为间接转换法，下面分别讨论这两种方法。

1. 直接转换法直接转换法通常用来消除尾递归和单向递归，将递归结构用循环结构来替代。

尾递归是指在递归算法中，递归调用语句只有一个，而且是处在算法的最后。

例如求阶乘的递归算法：long fact(int n){if (n==0) return 1;else return n*fact(n-1);}当递归调用返回时，是返回到上一层递归调用的下一条语句，而这个返回位置正好是算法的结束处，所以，不必利用栈来保存返回信息。

对于尾递归形式的递归算法，可以利用循环结构来替代。

例如求阶乘的递归算法可以写成如下循环结构的非递归算法：long fact(int n){int s=0;for (int i=1; i<=n;i++)s=s*i; //用s保存中间结果return s;}单向递归是指递归算法中虽然有多处递归调用语句，但各递归调用语句的参数之间没有关系，并且这些递归调用语句都处在递归算法的最后。

显然，尾递归是单向递归的特例。

例如求斐波那契数列的递归算法如下：int f(int n){if (n= =1 | | n= =0) return 1;else return f(n-1)+f(n-2);}对于单向递归，可以设置一些变量保存中间结构，将递归结构用循环结构来替代。

call GCD(28，6，X)执行过程
指令流方式

2.2 指令流方式 例2 GCD(100，18，x)执行write(x)的运行过 程，





2.2指令流方式 例3 对下面的递归过程， 写出调用P(3)的运行结果。 void P(int w)； { if (w>0) { P(w-1)； cout<<w<<endl； P(w-1)； } }
简化规则 1 如果递 归程序中只有一次递 归调用，则在转换时， 返回地址不入栈。
图4 例4的流程图
修改后的程序

void P1(int w)； { init(S)； while (w>0) { push(S, w)； w=w-1； } while( ! empty(S) ) { pop(S, w)； cout<<w<<endl； } }

a. 保留现场：开辟栈顶存储空间，用于保存返回地 址(不妨用Li，i=1，2，…)和调用层的形参和局部变 量的值(最外层调用不必考虑)；

b.准备数据：为被调子程序准备数据，计算实参值， 并赋给对应的形参；

c.执行goto L0； d.在返回处设一个标号Li(i=1，2，3，…)，并根据需要设 置以下语句：若函数有引用型形参或有返回值，从回传 变量中取出所保存的值，并传送到相应的实参或位置。
%
图6 例6的流程图

void GCD(int m, int n, int &h) { int temp,backvar; init(S); while n<>0 { push(S,m,n,h); temp= m; m= n; n=temp mod n; } h =m;cout<<h<<endl; while (!empty(S)) { backvar=h; pop(S,m,n,h); h=backvar; } }