用栈将递归转换成非递归数据结构与算法

如何用栈实现递归与非递归的转换

一.为什么要学习递归与非递归的转换的实现方法?
1)并不是每一门语言都支持递归的.
2)有助于理解递归的本质.
3)有助于理解栈,树等数据结构.

二.递归与非递归转换的原理.
递归与非递归的转换基于以下的原理:所有的递归程序都可以用树结构表示出来.需要说明的是,
这个"原理"并没有经过严格的数学证明,只是我的一个猜想,不过在至少在我遇到的例子中是适用的.
学习过树结构的人都知道,有三种方法可以遍历树:前序,中序,后序.理解这三种遍历方式的递归和非
递归的表达方式是能够正确实现转换的关键之处,所以我们先来谈谈这个.需要说明的是,这里以特殊的
二叉树来说明,不过大多数情况下二叉树已经够用,而且理解了二叉树的遍历,其它的树遍历方式就不难
了.
1)前序遍历

a)递归方式:

b)非递归方式

2)中序遍历

a)递归方式

b)非递归方式

3)后序遍历

a)递归方式

b)非递归方式

4)如何实现递归与非递归的转换
通常,一个函数在调用另一个函数之前,要作如下的事情:a)将实在参数,返回地址等信息传递
给被调用函数保存; b)为被调用函数的局部变量分配存储区; c)将控制转移到被调函数的入口.
从被调用函数返回调用函数之前,也要做三件事情:a)保存被调函数的计算结果; b)释放被调
函数的数据区; c)依照被调函数保存的返回地址将控制转移到调用函数.
所有的这些,不论是变量还是地址,本质上来说都是"数据",都是保存在系统所分配的栈中的.
ok,到这里已经解决了第一个问题:递归调用时数据都是保存在栈中的,有多少个数据需要保存
就要设置多少个栈,而且最重要的一点是:控制所有这些栈的栈顶指针都是相同的,否则无法实现
同步.
下面来解决第二个问题:在非递归中,程序如何知道到底要转移到哪个部分继续执行?回到上
面说的树的三种遍历方式,抽象出来只有三种操作:访问当前结点,访问左子树,访问右子树.这三
种操作的顺序不同,遍历方式也不同.如果我们再抽象一点,对这三种操作再进行一个概括,可以
得到:a)访问当前结点:对目前的数据进行一些处理; b)访问左子树:变换当前的数据以进行下一次
处理; c)访问右子树:再次变换当前的数据以进行下一次处理(与访问左子树所不同的方式).
下面以先序遍历来说明:

visit(T)这个操作就是对当前数据进行的处理, preorder_recursive(T->; lchild)就是把当前
数据变换为它的左子树,访问右子树的操作可以同样理解了.
现在回到我们提出的第二个问题:如何确定转移到哪里继续执行?关键在于一下三个地方:a)
确定对当前数据的访问顺序,简单一点说就是确定这个递归程序可以转换为哪种方式遍历的树结
构; b)确定这个递归函数转换为递归调用树时的分支是如何划分的,即确定什么是这个递归调用
树的"左子树"和"右子树"c)确定这个递归调用树何时返回,即确定什么结点是这个递归调用树的
"叶子结点".

三.三个例子
好了上面的理论知识已经足够了,下面让我们看看几个例子,结合例子加深我们对问题的认识
.即使上面的理论你没有完全明白,不要气馁,对事物的认识总是曲折的,多看多想你一定可以明
白(事实上我也是花了两个星期的时间才弄得比较明白得).

1)例子一:

下面按照我们上面说的,确定好递归调用树的结构,这一步是最重要的.首先,什么是叶子结点
,我们看到当n < 2时f = n + 1,这就是返回的语句,有人问为什么不是f = u1 * u2,这也是一个
返回的语句呀?答案是:这条语句是在u1 = exmp1((int)(n/2))和u2 = exmp1((int)(n/4))之后
执行的,是这两条语句的父结点. 其次,什么是当前结点,由上面的分析,f = u1 * u2即是父结点
.然后,顺理成章的u1 = exmp1((int)(n/2))和u2 = exmp1((int)(n/4))就分别是左子树和右子
树了.最后,我们可以看到,这个递归函数可以表示成后序遍历的二叉调用树.好了,树的情况分析
到这里,下面来分析一下栈的情况,看看我们要把什么数据保存在栈中,在上面给出的后序遍历的如果这个过程你没
非递归程序中我们已经看到了要加入一个标志域,因此在栈中要保存这个标志域; 另外,u1,u2和
每次调用递归函数时的n/2和n/4参数都要保存,这样就要分别有三个栈分别保存:标志域,返回量
和参数,不过我们可以做一个优化,因为在向上一层返回的时候,参数已经没有用了,而返回量也
只有在向上返回时才用到,因此可以把这两个栈合为一个栈.如果对于上面的分析你没有明白,建
议你根据这个递归函数写出它的递归栈的变化情况以加深理解,再次重申一点:前期对树结构和
栈的分析是最重要的,如果你的程序出错,那么请返回到这一步来再次分析,最好把递归调用树和
栈的变化情况都画出来,并且结合一些简单的参数来人工分析你的算法到底出错在哪里.
ok,下面给出我花了两天功夫想出来的非递归程序(再次提醒你不要气馁,大家都是这么过来
的).

算法分析:a)flag只有三个可能值:0表示第一次访问该结点,1表示访问的是左子树,2表示
已经结束了对某一棵子树的访问,可能当前结点是这棵子树的右子树,也可能是叶子结点.b)每
遍历到某个结点的时候,如果这个结点满足叶子结点的条件,那么把它的flag域设为2; 否则根据
访问的是根结点,左子树或是右子树来设置flag域,以便决定下一次访问该节点时的程序转向.

2)例子二

快速排序算法
递归算法如下:

需要说明一下快速排序的算法: partition函数根据数组中的某一个数把数组划分为两个部分,
左边的部分均不大于这个数,右边的数均不小于这个数,然后再对左右两边的数组再进行划分.这
里我们专注于递归与非递归的转换,partition函数在非递归函数中同样的可以调用(其实
partition函数就是对当前结点的访问).
再次进行递归调用树和栈的分析:
递归调用树:a)对当前结点的访问是调用partition函数; b)左子树:
qsort_recursive(array, low, p - 1); c)右子树:qsort_recursive(array, p + 1, high);
d)叶子结点:当low < high时; e)可以看出这是一个先序调用的二叉树
栈:要保存的数据是两个表示范围的坐标.

3)例子三
阿克曼函数:

递归算法如下:

这个例子相对难一些,不过只要正确的分析递归调用树和栈的变化情况就不难解决,先卖个关子,晚上再来公布答案,感兴趣的可以先想想.

mirnshi 回复于：2004-05-25 00:15:35

引用：原帖由 "converse" 发表：

这个例子相对难一些,不过只要正确的分析递归调用树和栈的变化情况就不难解决,先卖个关子,晚上再来公布答案,感兴趣的可以先想想.

递归和非递归, 其实都是一样的.非递归需要人为构建维护堆栈.递归只是系统
在帮你维护堆栈而已. 数据结构上说得很清楚.

五月回复于：2004-05-25 11:27:42

即使不是递归设计，但你仍然在用递归的思想在写东西。：）
另外，尾递归的改写可以不用栈。

converse 回复于：2004-05-25 15:32:18

好了,让我们回到递归与非递归的世界中,继续未完的旅途.

这道题的难点就是确定递归调用树的情况,因为从akm函数的公式可以看到,有三个递归调用,一般
而言,有几个递归调用就会有几棵递归调用的子树,不过这只是一般的情况,不一定准确,也不一定非要
机械化的这么作,因为通常情况下我们可以做一些优化,省去其中的一些部分,这道题就是一个例子.
递归调用树的分析:a)是当m=0时是叶子结点; b)左子树是akm(m - 1, akm(m, n - 1))调用中的
akm(m, n - 1)调用,当这个调用结束得出一个值temp时,再调用akm(m - 1, temp),这个调用是右子树
.c)从上面的分析可以看出,这个递归调用树是后序遍历的树.
栈的分析:要保存的数据是m, n,当n = 0 或 m = 0时开始退栈,当n = 0时把上一层栈的m值变为
m - 1,n变为1，当m = 0时把上一层栈的m值变为0,n变为n + 1.从这个分析过程可以看出,我们省略了
当n = 0时的akm(m - 1, 1)调用,原来在系统机械化的实现递归调用的过程中,这个调用也是一棵子树,
不过经过分析,我们用修改栈中数据的方式进行了改进.

crazybaw 回复于：2004-05-25 15:42:24

最近看了本书,中文名字; (pointers on c),一外国人写的,在这本书中,对于递归等介绍了一些,也有一些堆栈调用的图,比较适合我们新人读啊.

converse 回复于：2004-05-25 16:34:59

三.递归程序的分类及用途

递归程序分为两类:尾部递归和非尾部递归.上面提到的几个例子都是非尾部递归,在一个选择分支中有至少
一个的递归调用.相对而言,尾部递归就容易很多了,因为与非尾部递归相比,每个选择分支只有一个递归调用,
我们在解决的时候就不需要使用到栈,只要循环和设置好循环体就可以了.下面再举几个尾部递归的例子吧,比较
简单我就不多说什么了.

1)例子一

a)递归程序

b)非递归程序

2)例子二

a)递归程序

b)非递归程序

分析完了递归程序的分类,让我们回头看看在向非递归转换的过程中用到了什么来实现转换:
1)循环,因为程序要在某个条件下一直执行下去,要代替递归程序,循环必不可少,对于尾部递归,循环结束的
条件十分容易确定,只要按照不同分支的条件写出来就可以了.而对于非尾部递归程序,循环结束的条件一
般是当栈为空时或者是结束了对递归调用树的遍历从树的根结点退出时,而且有的时候写成while()的形式
,有时写成do ...while的形式(如上面的akm函数),具体怎样,很难说清楚,取决于你对整个递归程序的分析
.
2)递归调用树,树的结构在转换的过程中是不可见的,你不必为转换专门写一个树结构,不过能不能把递归调用
中的树遍历方式以及叶子结点,左子树,右子树等元素确定好是你能否正确解决问题的关键(这一点已经在
上面的分析过程中展露无疑),确定好这些后,剩下的工作大部分就是按照给出的几种不同的遍历树的方式
把程序进行改写,这个过程就考验你对树结构还有遍历方式是否很好的掌握了(看出基础的重要了吗?如果
回答是,那么和我一样好好的打好基础吧,一切都还不晚!!).对于尾部递归而言,可以看作没有递归调用树,
所以尾部递归的难度大大降低了.
3)栈,非尾部调用中需要栈来保存数据,这一点已经很清楚了,需要注意几个问题:a)栈有时可能会出现不够的
情况,拿上面的akm函数来说,我用的50个元素的数组,你如果把m和n值设置得大一些,这个栈就不能用了,有
时你的算法正确了,不过没有注意到这个问题还是会出错的; 反过来说,在递归调用中,系统或者编译器的优
化功能不够好的化,在这个栈上可能会消耗很多空间,这个时候如果你把程序改成非递归的形式,然后再用
动态分配技术分配栈可能就会把程序的性能提高一大块--这也是我们学习这门技术的意义之一,因为系统
是机械化的,你如果知道更好的优化办法,为什么不用呢?

什么时候可以用递归解决问题?到了这一步,如果你对于上面说的已经相当明白的话,这个问题不难回答,如果
我们要解决的问题要分成几个小的部分,而其中的一些与你要解决的问题是一样的,只不过是问题的规模(如
参数等)小了,那么这样的问题可以用递归来解决.根据问题设计好一个递归是所有这些的基础,转换也是在原
来的递归程序上进行的,所以这一步一定要做好.通常,设计一个递归程序要注意一下几个问题:a)可以递归解
决的问题是什么?b)入口和出口参数是什么--即要明确好出入的接口.

四.学习过程中参考到的一些资料

1)<<算法导论>; >; 国防科大出版社张益新沈雁编著
这本书比较老了,也许很难找了,不过参考价值不大,里面专门用了一章来讲这个问题,可惜用的是goto来实
现递归调用的选择分支(所以我说参考价值不大),如果没有也无所谓的.

2)http://db.pku.edu.cn/mzhang/北京大学张铭老师的主页.
上面可以找到一个张老师讲解递归和非递归转换的视频,有大概50多分钟吧,我没有听完,原先看第一本书
的对于如何不用goto实现选择分支十分不解,张老师讲到的递归调用树真正让我豁然开朗,从此以后虽然还
是有很多问题,不过明白了这个大体的解决思路就有了.

3)<<数据结构>; >; 清华大学出版社严蔚敏著
这本书讲到栈的时候略微讲到了一些这方面的内容,网上可以找到一位叫一具的仁兄写的这本书的习题解答
,可以自己去找一找,我的中序和后序遍历的算法完全看的他写的.

4) http://www.tztvu.edu.cn/kfjy/bkjy/jsj/bxk/sjjg/kcdh/忘了是什么的网页了
里面的一个dn5.doc的文件中有讲解转换akm函数的方法,给我的启发很大,如果你对于我说的akm函数还有疑
问,那么可以看看人家写的,他把递归调用树和栈的变化情况都写出来了,非常直观.