如何用栈实现递归与非递归的转换(doc 24)

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