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

递归与非递归转换的基础知识是能够正确理解三种树的遍历方法：前序，中序和后序，第一篇就是关于这三种遍历方法的递归和非递归算法。一、为什么要学习递归与非递归的转换的实现方法? 1)并不是每一门语言都支持递归的。 2)有助于理解递归的本质。 3)有助于理解栈，树等数据结构。二、三种遍历树的递归和非递归算法 递归与非递归的转换基于以下的原理：所有的递归程序都可以用树结构表示出来。需要说明的是，这个”原理”并没有经过严格的数学证明，只是我的一个猜 想，不过在至少在我遇到的例子中是适用的。学习过树结构的人都知道，有三种方法可以遍历树：前序，中序，后序。理解这三种遍历方式的递归和非递归的表达方 式是能够正确实现转换的关键之处，所以我们先来谈谈这个。需要说明的是，这里以特殊的二叉树来说明，不过大多数情况下二叉树已经够用，而且理解了二叉树的 遍历，其它的树遍历方式就不难了。 1)前序遍历 a)递归方式： void preorder_recursive(Bitree T) /* 先序遍历二叉树的递归算法 */ if (T) visit(T); /* 访问当前结点 */ preorder_recursive(T-lchild); /* 访问左子树 */ preorder_recursive(T-rchild); /* 访问右子树 */ b)非递归方式 void preorder_nonrecursive(Bitree T) /* 先序遍历二叉树的非递归算法 */ initstack(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 inorder_recursive(Bitree T) /* 中序遍历二叉树的递归算法 */ if (T) inorder_recursive(T-lchild); /* 访问左子树 */ visit(T); /* 访问当前结点 */ inorder_recursive(T-rchild); /* 访问右子树 */ b)非递归方式 void inorder_nonrecursive(Bitree T) initstack(S); /* 初始化栈 */ push(S,T); /* 根指针入栈 */ while (!stackempty(S) while (gettop(S, p) & p) /* 向左走到尽头 */ push(S,p-lchild); pop(S,p); /* 空指针退栈 */ if (!stackempty(S) pop(S,p); visit(p); /* 访问当前结点 */ push(S,p-rchild); /* 向右走一步 */ 3)后序遍历 a)递归方式 void postorder_recursive(Bitree T) /* 中序遍历二叉树的递归算法 */ if (T) postorder_recursive(T-lchild); /* 访问左子树 */ postorder_recursive(T-rchild); /* 访问右子树 */ visit(T); /* 访问当前结点 */ b)非递归方式 typedef struct BTNode* ptr; enum 0,1,2 mark; PMType; /* 有mark域的结点指针类型 */ void postorder_nonrecursive(BiTree T) /* 后续遍历二叉树的非递归算法 */ PMType a; initstack(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); /* 访问左子树 */ break; case 1: push(S,a,pt,2); /* 修改mark域 */ if(a.ptr-rchild) push(S,a.ptr-rchild,0); /* 访问右子树 */ break; case 2: visit(a.ptr); /* 访问结点 */ 三、实现递归与非递归的换转原理和例子一）原理分析 通常，一个函数在调用另一个函数之前，要作如下的事情：a)将实在参数，返回地址等信息传递给被调用函数保存; b)为被调用函数的局部变量分配存储区;c)将控制转移到被调函数的入口。 从被调用函数返回调用函数之前，也要做三件事情：a)保存被调函数的计算结果;b)释放被调函数的数据区;c)依照被调函数保存的返回地址将控制转移到调用函数。所有的这些，不论是变量还是地址，本质上来说都是”数据”，都是保存在系统所分配的栈中的。 ok，到这里已经解决了第一个问题：递归调用时数据都是保存在栈中的，有多少个数据需要保存就要设置多少个栈，而且最重要的一点是：控制所有这些栈的栈顶指针都是相同的，否则无法实现同步。 下面来解决第二个问题：在非递归中，程序如何知道到底要转移到哪个部分继续执行?回到上面说的树的三种遍历方式，抽象出来只有三种操作：访问当前结点，访 问左子树，访问右子树。这三种操作的顺序不同，遍历方式也不同。如果我们再抽象一点，对这三种操作再进行一个概括，可以得到：a)访问当前结点：对目前的 数据进行一些处理;b)访问左子树：变换当前的数据以进行下一次处理;c)访问右子树：再次变换当前的数据以进行下一次处理(与访问左子树所不同的方 式)。 下面以先序遍历来说明： void preorder_recursive(Bitree T) /* 先序遍历二叉树的递归算法 */ if (T) visit(T); /* 访问当前结点 */ preorder_recursive(T-lchild); /* 访问左子树 */ preorder_recursive(T-rchild); /* 访问右子树 */ visit(T)这个操作就是对当前数据进行的处理， preorder_recursive(T-lchild)就是把当前 数据变换为它的左子树，访问右子树的操作可以同样理解了。 现在回到我们提出的第二个问题：如何确定转移到哪里继续执行?关键在于一下三个地方：a)确定对当前数据的访问顺序，简单一点说就是确定这个递归程序可以 转换为哪种方式遍历的树结构;b)确定这个递归函数转换为递归调用树时的分支是如何划分的，即确定什么是这个递归调用树的”左子树”和”右子树”c)确定 这个递归调用树何时返回，即确定什么结点是这个递归调用树的”叶子结点”。 二）两个例子 好了上面的理论知识已经足够了，下面让我们看看几个例子，结合例子加深我们对问题的认识。即使上面的理论你没有完全明白，不要气馁，对事物的认识总是曲折的，多看多想你一定可以明白(事实上我也是花了两个星期的时间才弄得比较明白得)。 1)例1： f(n) = n + ; (n = 2); 这个例子相对简单一些，递归程序如下： int f_recursive(int n) int u1, u2, f; if (n 2) f = n + 1; else u1 = f_recursive(int)(n/2); u2 = f_recursive(int)(n/4); f = u1 * u2; return f; 下面按照我们上面说的，确定好递归调用树的结构，这一步是最重要的。首先，什么是叶子结点，我们看到当n = 0) switch(flagcp) case 0: /* 访问的是根结点 */ if (stackcp = 2) /* 左子树入栈 */ flagcp = 1; /* 修改标志域 */ cp+; stackcp = (int)(stackcp - 1 / 2); flagcp = 0; else /* 否则为叶子结点 */ stackcp += 1; flagcp = 2; break; case 1: /* 访问的是左子树 */ if (stackcp = 2) /* 右子树入栈 */ flagcp = 2; /* 修改标志域 */ cp += 2; stackcp = (int)(stackcp - 2 / 4); flagcp = 1; else /* 否则为叶子结点 */ stackcp += 1; flagcp = 2; break; case 2: /* */ if (flagcp - 1 = 2) /* 当前是右子树吗? */ /* * 如果是右子树， 那么对某一棵子树的后序遍历已经 * 结束，接下来就是对这棵子树的根结点的访问 */ stackcp-2 = stackcp * stackcp -1; flagcp - 2 = 2; cp = cp - 2; else /* 否则退回到后序遍历的上一个结点 */ cp-; break; return stack0; 算法分析：a)flag只有三个可能值：0表示第一次访问该结点，1表示访问的是左子树，2表示已经结束了对某一棵子树的访问，可能当前结点是这棵子树的 右子树，也可能是叶子结点。b)每遍历到某个结点的时候，如果这个结点满足叶子结点的条件，那么把它的flag域设为2;否则根据访问的是根结点，左子树 或是右子树来设置flag域，以便决定下一次访问该节点时的程序转向。 2)例2: 快速排序算法递归算法如下： void swap(int array， int low， int high) int temp; temp = arraylow; arraylow = arrayhigh; arrayhigh = temp; int partition(int array， int low， int high) int p; p = arraylow; while (low high) while (low = p) high-; swap(array，low，high); while (low high & arraylow = p) low+; swap(array，low，high); return low; void qsort_recursive(int array， int low， int high) int p; if(low high) p = partition(array， low， high); qsort_recursive(array， low， p - 1); qsort_recursive(array， p + 1， high); 需要说明一下快速排序的算法： partition函数根据数组中的某一个数把数组划分为两个部分，左边的部分均不大于这个数，右边的数均不小于这个数，然后再对左右两边的数组再进行划 分。这里我们专注于递归与非递归的转换，partition函数在非递归函数中同样的可以调用(其实partition函数就是对当前结点的访问)。 再次进行递归调用树和栈的分析： 递归调用树：a)对当前结点的访问是调用partition函数;b)左子树：qsort_recursive(array， low， p - 1);c)右子树：qsort_recursive(array， p +1， high); d)叶子结点：当low high时;e)可以看出这是一个先序调用的二叉树。栈：要保存的数据是两个表示范围的坐标。 代码：void qsort_nonrecursive(int array， int low， int high) int m50， n50， cp， p; cp = 0; m0 = low; n0 = high; /* 初始化栈和栈顶指针 */ while (mcp ncp) while (mcp = 0) = g(m - 1， 2n) + n; (m 0， n = 0)a)递归程序 int g_recursive(int m， int n) if (m = 0 & n = 0) return 0; return (g_recurse(m - 1， 2*n) + n); b)非递归程序 int g_nonrecursive(int m， int n) int p; for (p = 0; m 0 & n = 0; m-， n *= 2) p += n; return p; 2)例2: f(n) = n + 1 (n = 0) = n * f(n/2) (n 0)a)递归程序 int f_recursive(int n) if (n = 0) return 1; return (n * f_recurse(n/2); b)非递归程序 int f_nonrecursive(int n) int m; for (m = 1; n 0; n /= 2) m *= n; return m+; 分析完了递归程序的分类，让我们回头看看在向非递归转换的过程中用到了什么来实现转换： 1)循环，因为程序要在某个条件下一直执行下去，要代替递归程序，循环必不可少，对于尾部递归，循环结束的条件十分容易确定，只要按照不同分支的条件写出 来就可以了。而对于非尾部递归程序，循环结束的条件一般是当栈为空时或者是结束了对递归调用树的遍历从树的根结点退出时，而且有的时候写成while() 的形式，有时写成do 。while的形式(如上面的akm函数)，具体怎样，很难说清楚，取决于你对整个递归程序的分析。 2)递归调用树，树的结构在转换的过程中是不可见的，你不必为转换专门写一个树结构，不过能不能把递归调用中的树遍历方式以及叶子结点，左子树，右子树等 元素确定好是你能否正确解决问题的关键(这一点已经在上面的分析过程中展露无疑)，确定好这些后，剩下的工作大部分就是按照给出的几种不同的遍历树的方式 把程序进行改写，这个过程就考验你对树结构还有遍历方式是否很好的掌握了(看出基础的重要了吗?如果回答是，那么和我一样好好的打好基础吧，一切都还不 晚!)。对于尾部递归而言，可以看作没有递归调用树，所以尾部递归的难度大大降低了。 3)栈，非尾