数据结构与算法—递归与非递归转换

1、递归与非递归转换的基础知识是能够正确理解三种树的遍历方法：前序，中序和后序，第一篇就是关于这三种遍历方法的递归和非递归算法。一、 为什么要学习递归与非递归的转换的实现方法？1>并不是每一门语言都支持递归的。2>有助于理解递归的本质。3>有助于理解栈，树等数据结构。二、三种遍历树的递归和非递归算法递归与非递归的转换基于以下的原理：所有的递归程序都可以用树结构表示出来。需要说明的是，这个”原理”并没有经过严格的数学证明，只是我的一个猜想，不过在至少在我遇到的例子中是适用的。学习过树结构的人都知道，有三种方法可以遍历树：前序，中 序，后序。理解这三种遍历方式的递归和非递归的表达方式

2、是能够正确实现转换的关键之处，所以我们先来谈谈这个。需要说明的是，这里以特殊的二叉树来说明，不过大多数情 况下二叉树已经够用，而且理解了二叉树的遍历，其它的树遍历方式就不难了。1>前序遍历a>递归方式：void preorder_recursive(Bitree T> /*先序遍历二叉树的递归算法*/if (T> visit(T>。/* 访问当前结点*/preorder_recursive(T->lchild>。/* 访问左子树 */preorder_recursive(T->rchild>。/* 访问右子树 */b>非递归方式法*/

3、in itstack(S> 。push(S,T> 。/*根指针进栈*/while(!stackempty(S>> while(gettop(S,p>&&p> /*向左走到尽头 */visit(p>。/*每向前走一步都访问当前结点*/push(S,p->lchild>。pop(S,p> 。if(!stackempty(S>> /*向右走一步 */pop(S,p>。push(S,p->rchild>。2>中序遍历a>递归方式中序遍历二叉树的递归算法*/void ino rder_r

4、ecursive(Bitree T>/* if (T> inorder_recursive(T->lchild>。/*访问左子树 */visit(T> 。/* 访问当前结点*/b非递归方式void ino rder_ non recursive(Bitree T>in itstack(S>/*初始化栈*/push(S,T> 。/*根指针入栈*/while (!stackempty(S>> while (gettop(S, p> && p>/*向左走到尽头*/push(S,p->lchild>po

5、p(S,p>/*空指针退栈*/if (!stackempty(S>> pop(S,p>visit(p>。 /*访问当前结点*/push(S,p->rchild>。/*向右走,步*/3后序遍历a递归方式void postorder_recursive(Bitree T>/*中序遍历二叉树的递归算法*/if (T> */visit(T>/*访问当前结点*/b>非递归方式typedef struct BTNode* ptrenum 0,1,2 mark PMType 。/*有mark域的结点指针类型*/void postorder_

6、non recursive(BiTree T>/*后续遍历二叉树的非递归算法PMType ain itstack(S>/* S的元素为PMType类型*/push (S,T,0>/*根结点入栈*/while(!stackempty(S>> pop(S,a>switch(a,mark>case 0:push(S,a.ptr，1>。/* 修改mark域*/if(a.ptr->lchild>push(S,a,ptr->lchild,0>/*访问左子树*/breakcase 1:push(S,a,pt,2。/* 修改 mark 域

7、 */if(a.ptr-rchildpush(S,a.ptr-rchild,O。 /* 访问右子树 */break。case 2:visit(a.ptr。/*访问结点 */三、实现递归与非递归的换转原理和例子一)原理分析通常，一个函数在调用另一个函数之前，要作如下的事情：a将实在参数，返回地址等信息传递给被调用函数保存。b为被调用函数的局部变量分配存储区。c将控制转移到被调函数的入口。从被调用函数返回调用函数之前，也要做三件事情：a保存被调函数的计算结果。b释放被调函数的数据区。c依照被调函数保存的返回地址将控制转移到调用函数。所有的这些，不论是变量还是地址，本质上来说都是”数据”都是保存在系

8、统所分配的栈中的。ok，到这里已经解决了第一个问题：递归调用时数据都是保存在栈中的，有多少个数据需要保存就要设置多少个栈，而且最重要的一点是：控制所有这些栈的栈顶指针都 是相同的，否则无法实现同步。下面来解决第二个问题：在非递归中，程序如何知道到底要转移到哪个部分继续执行？回到上面说的树的三种遍历方式，抽象出来只有三种操作：访问当前结点，访问左子树，访问右子树。这三种操作的顺序不同，遍历方式也不同。如果我们再抽象一点，对 这三种操作再进行一个概括，可以得到：a访问当前结点：对目前的数据进行一些处理。b访问左子树：变换当前的数据以进行下一次处理。c访问右子树：再次变换当前的数据以进行下一次处理(

9、与访问左子树所不同的方式。F面以先序遍历来说明:if (T> visit(T>/* 访问当前结点*/* 访问左子树*/* 访问右子树*/preorder_recursive(T->lchild> preorder_recursive(T->rchild>visit(T>这个操作就是对当前数据进行的处理，preorder_recursive(T->lchild>就是把当前 数据变换为它的左子树，访问右子树的操作可以同样理解了。现在回到我们提出的第二个问题：如何确定转移到哪里继续执行？关键在于一下三个地方：a>确定对当前数据的访问顺序，简

10、单一点说就是确定这个递归程序可以转换为哪种方式遍历的树结构。b>确定这个递归函数转换为递归调用树时的分支是如何划分的， 即确定什么是这个递归调用树的”左子树”和”右子树” c>确定 这个递归调用树何时返回，即确定什么结点是这个递归调用树的”叶子结点”。二)两个例子好了上面的理论知识已经足够了，下面让我们看看几个例子，结合例子加深我们 对问题的认识。即使上面的理论你没有完全明白，不要气馁，对事物的认识总是曲折的， 多看多想你一定可以明白(事实上我也是花了两个星期的时间才弄得比较明白得>。1> 例 1 :f(n> = n +1。 (n <2 >=fn /2

11、 + fn /4(n >= 2>这个例子相对简单一些，递归程序如下：int f_recursive(i nt n>int u1, u2, f。if (n < 2>f = n + 1。else u1 = f_recursive(i nt>(n/2>> u2 = f_recursive(i nt>(n/4>> f = u1 * u2 。return f 。下面按照我们上面说的，确定好递归调用树的结构，这一步是最重要的。首先，什么是叶子结点，我们看到当n < 2 时f= n + 1，这就是返回的语句，有人问为什么不是f = u1

12、 * u2，这也是一个返回的语句呀 ？答案是：这条语句是在 u1 = exmp1(int>(n/2>> 和u2 = exmp1(int>(n/4>>之后 执行的，是这两条语句的父结点。其次，什么是当前结点，由上面的分析，f = u1 * u2即是父结点。然后，顺理成章的 u1 = exmp1(int>(n/2>>和 u2 = exmp1(int>(n/4>>就分别是左子树和右子树了。最后，我们可以看到，这个递归函数可以表示成后序遍历的 二叉调用树。好了，树的情况分析到这里，下面来分析一下栈的情况，看看我们要把什么数据保存在

13、栈中：非递归程序中我们已经看到了要加入一个标志域，因此在栈中要保存这个标志域。另外，u1，u2和每次调用递归函数时的n/2和n/4参数都要保存，这样就要分别有三个栈分别保存：标志域，返回量和参数，不过我们可以做一个优化，因为在向上一层 返回的时候，参数已经没有用了，而返回量也只有在向上返回时才用至打因此可以把这两个栈合为一个栈。如果对于上面的分析你没有明白，建议你根据这个递归函数写出它的递 归栈的变化情况以加深理解，再次重申一点：前期对树结构和栈的分析是最重要的，如果你的程序出错，那么请返回到这一步来再次分析，最好把递归调用树和栈的变化情况都画 出来，并且结合一些简单的参数来人工分析你的算法到

14、底出错在哪里。ok，下面给出我花了两天功夫想出来的非递归程序(再次提醒你不要气馁，大家都是这么过来的>。代码:int stack20,flag20, cp。/*初始化栈和栈顶指针*/cp = 0。stack0 = n。flag0 =0。while(cp >= 0>switch(flagcp> case 0:/*访问的是根结点*/if (stackcp>=2> /*左子树入栈 */flagcp=:1 。 /*修改标志域*/cp+。stackcp=(i nt>(stackcp - 1 /2>。flagcp=:0 。 else /*否则为叶子结点*/s

15、tackcp += 1flagcp = 2。break。case 1:/*访问的是左子树*/if (stackcp >= 2>/*右子树入栈 */flagcp = 2。/* 修改标志域*/cp +=2。4> 。stackcp =(in t>(stackcp - 2 /flagcp = 1。 else /*否则为叶子结点*stackcp += 1。flagcp = 2。break。case 2:/* */子树吗？ */if (flagcp -1 =2> /*当前是右/* *如果是右子树，那么对某一棵子树的后序遍历已经*结束，接下来就是对这棵子树的根结点的访问*/1。

16、stackcp-2 = stackcp * stackcp -flagcp - 2=2。cp = cp - 2。 else/*否则退回到后序遍历的上一个结点*/cp-。breakreturn stackO算法分析：a>flag只有三个可能值：0表示第一次访问该结点，1表示访问的是 左子树，2表示已经结束了对某一棵子树的访问，可能当前结点是这棵子树的右子树，也可能是叶子结点。b>每遍历到某个结点的时候，如果这个结点满足叶子结点的条件，那么 把它的flag域设为2。否则根据访问的是根结点，左子树或是右子树来设置flag域，以便决定下一次访问该节点时的程序转向。2> 例 2:int

17、 low ， int high>快速排序算法递归算法如下:void swap(i nt arrayint temp 。temp = arraylow arraylow = arrayhigh arrayhigh = tempint partiti on (i nt array， int low ， int high>int p 。p = arraylow 。while (low < high> while (low < high && arrayhigh >= p>high_-swap(array , low , high> 。

18、while (low < high && arraylow <= p> low+ 。swap(array , low , high> 。return low 。int low , int high>low , high> 。,low , p - 1>。,p + 1, high> 。void qsort_recursive(i nt arrayint p 。if(low < high> p = partiti on( arrayqsort_recursive(arrayqsort_recursive(array需要说明一

19、下快速排序的算法：partiti on函数根据数组中的某一个数把数组划分为两个部分，左边的部分均不大于这个数，右边的数均不小于这个数，然后再对左右两边 的数组再进行划分。这里我们专注于递归与非递归的转换，partition函数在非递归函数中同样的可以调用(其实partition函数就是对当前结点的访问>。再次进行递归调用树和栈的分析：递归调用树：a>对当前结点的访问是调用partition 函数。b> 左子树： qsort_recursive(array ， low ， p - 1>。 c> 右子树： qsort_recursive(array ， p +1， h

20、igh> 。 d> 叶子结点：当 low < high 时。e> 可以看出这是一个先序调用的二叉树。栈：要保存的数据是两个表示范围的坐标。代码:void qsort_ non recursive(i nt arrayint low , int highint m50, n50 , cp , p。cp = 0。m0 = low 。n0 = high 。 /* 初始化栈和栈顶指针 */while (mcp < n cp> while (mcp < n cp> /*向左走到尽头 */p = partition(array, mcp , ncp>。

21、 /* 对当前结点的访问 */cp+ 。mcp = mcp - 1。n cp = p - 1。/*向右走一步*/mcp + 1 = n cp + 2。ncp + 1 = ncp - 1。cp+ 。四、递归程序的分类及用途递归程序分为两类：尾部递归和非尾部递归。上面提到的几个例子都是非尾部递 归，在一个选择分支中有至少一个的递归调用。相对而言，尾部递归就容易很多了，因为 与非尾部递归相比，每个选择分支只有一个递归调用，我们在解决的时候就不需要使用到栈，只要循环和设置好循环体就可以了。下面再举 几个尾部递归的例子吧，比较简单我就不多说什么了。1> 例 1:g(m , n> = 0 (m

22、 = 0, n >= 0>=g(m - 1, 2n> + n 。(m > 0,a>递归程序int g_recursive(i nt m , int n>if (m = 0 && n >= 0>return 0。return (g_recurse(m - 1, 2*n> + n>b>非递归程序int g_non recursive(i nt m, int n>int p 。for (p = 0。 m > 0 && n >= 0。 m-,p += n 。return p 。2>

23、 例 2:f(n> = n + 1 (n = 0>n >= 0>n *= 2>=n * f(n/2> (n > 0>a>递归程序int f_recursive(i nt n>if (n = 0>return 1。return (n * f_recurse( n/2>>。b>非递归程序int f_non recursive(i nt n>int m 。for (m = 1。n > 0 。n /= 2>m *= n 。return m+。分析完了递归程序的分类，让我们回头看看在向非递归转换的过程中

24、用到了什么来实现转换：1>循环，因为程序要在某个条件下一直执行下去，要代替递归程序，循环必不可 少，对于尾部递归，循环结束的条件十分容易确定，只要按照不同分支的条件写出来就可以了。而对于非尾部递归程序，循环结束的条件一般是当栈为空时或者是结束了对递归调 用树的遍历从树的根结点退出时，而且有的时候写成while(>的形式，有时写成 do。while的形式(如上面的akm函数 >，具体怎样，很难说清楚，取决于你对整个递 归程序的分析。2递归调用树，树的结构在转换的过程中是不可见的，你不必为转换专门写一个 树结构，不过能不能把递归调用中的树遍历方式以及叶子结点，左子树，右子树等元素确定好是你能否正确解决问题的关键（这一点已经在上面的分析过程中展露无疑，确定好这些后，剩下的工作大部分就是按照给出的几种不同的遍历树的方式把程序进行改写，