如何用栈实现递归与非递归的转换(转) - 网络工程3班- 博客园

 

原文地址

 

 

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

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

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

  1. void preorder_recursive(Bitree T)                /* 先序遍历二叉树的递归算法 */
  2.                 {
  3.                         if (T) {
  4.                                 visit(T);                         /* 访问当前结点 */
  5.                                 preorder_recursive(T->;lchild);        /* 访问左子树 */
  6.                                 preorder_recursive(T->;rchild);        /* 访问右子树 */
  7.                         }
  8.                 }
复制代码

                               
                b)非递归方式
       
  1. void preorder_nonrecursive(Bitree T)                /* 先序遍历二叉树的非递归算法 */
  2.                 {
  3.                         initstack(S);
  4.                         push(S,T);                                 /* 根指针进栈 */
  5.                         while(!stackempty(S)) {
  6.                                 while(gettop(S,p)&&p) {                /* 向左走到尽头 */
  7.                                         visit(p);                /* 每向前走一步都访问当前结点 */
  8.                                         push(S,p->;lchild);
  9.                                 }
  10.                                 pop(S,p);
  11.                                 if(!stackempty(S)) {                /* 向右走一步 */
  12.                                         pop(S,p);
  13.                                         push(S,p->;rchild);
  14.                                 }
  15.                         }
  16.                 }
复制代码


               
        2)中序遍历

                a)递归方式

       
  1. void inorder_recursive(Bitree T)                /* 中序遍历二叉树的递归算法 */
  2.                 {
  3.                         if (T) {
  4.                                 inorder_recursive(T->;lchild);        /* 访问左子树 */
  5.                                 visit(T);                         /* 访问当前结点 */
  6.                                 inorder_recursive(T->;rchild);        /* 访问右子树 */
  7.                         }
  8.                 }
复制代码

               
                b)非递归方式
       
  1. void  inorder_nonrecursive(Bitree T)
  2.                 {
  3.                         initstack(S);                                /* 初始化栈 */
  4.                         push(S, T);                                /* 根指针入栈 */
  6.                         while (!stackempty(S)) {                       
  7.                                 while (gettop(S, p) && p)         /* 向左走到尽头 */
  8.                                         push(S, p->;lchild);
  9.                                 pop(S, p);                        /* 空指针退栈 */
  10.                                 if (!stackempty(S)) {
  11.                                         pop(S, p);
  12.                                         visit(p);                /* 访问当前结点 */
  13.                                         push(S, p->;rchild);        /* 向右走一步 */
  14.                                 }
  15.                         }
  16.                 }
复制代码

               
        3)后序遍历

                a)递归方式
       
  1. void postorder_recursive(Bitree T)                /* 中序遍历二叉树的递归算法 */
  2.                 {
  3.                    if (T) {
  4.                            postorder_recursive(T->;lchild);        /* 访问左子树 */
  5.                            postorder_recursive(T->;rchild);        /* 访问右子树 */
  6.                            visit(T);                                 /* 访问当前结点 */
  7.                    }
  8.                 }
复制代码

               
                b)非递归方式
       
  1. typedef struct {
  2.                         BTNode* ptr;
  3.                         enum {0,1,2} mark;
  4.                 } PMType;                                         /* 有mark域的结点指针类型 */
  6.                 void postorder_nonrecursive(BiTree T)                /* 后续遍历二叉树的非递归算法 */
  7.                 {
  8.                         PMType a;
  9.                         initstack(S);                                 /* S的元素为PMType类型 */
  10.                         push (S,{T,0});                         /* 根结点入栈 */
  11.                         while(!stackempty(S)) {
  12.                                 pop(S,a);
  13.                                 switch(a.mark)
  14.                                 {
  15.                                 case 0:
  16.                                         push(S,{a.ptr,1});         /* 修改mark域 */
  17.                                         if(a.ptr->;lchild)
  18.                                                 push(S,{a.ptr->;lchild,0}); /* 访问左子树 */
  19.                                         break;
  20.                                 case 1:
  21.                                         push(S,{a.ptr,2});         /* 修改mark域 */
  22.                                         if(a.ptr->;rchild)
  23.                                                 push(S,{a.ptr->;rchild,0}); /* 访问右子树 */
  24.                                         break;
  25.                                 case 2:
  26.                                         visit(a.ptr);                 /* 访问结点 */
  27.                                 }
  28.                         }
  29.                 }
复制代码

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

   visit(T)这个操作就是对当前数据进行的处理, preorder_recursive(T->;lchild)就是把当前
        数据变换为它的左子树,访问右子树的操作可以同样理解了.
           现在回到我们提出的第二个问题:如何确定转移到哪里继续执行?关键在于一下三个地方:a)
        确定对当前数据的访问顺序,简单一点说就是确定这个递归程序可以转换为哪种方式遍历的树结
        构;b)确定这个递归函数转换为递归调用树时的分支是如何划分的,即确定什么是这个递归调用
        树的"左子树"和"右子树"c)确定这个递归调用树何时返回,即确定什么结点是这个递归调用树的
        "叶子结点".
       
        三.三个例子
           好了上面的理论知识已经足够了,下面让我们看看几个例子,结合例子加深我们对问题的认识
        .即使上面的理论你没有xx明白,不要气馁,对事物的认识总是曲折的,多看多想你一定可以明
        白(事实上我也是花了两个星期的时间才弄得比较明白得).
          
        1)例子一:
  1. f(n) = 　n + １;        (n <２)　
  2.         　　　　 f[n/2] + f[n/4](n >;= 2);
  3.        
  4.         这个例子相对简单一些,递归程序如下:
  5.         int        f_recursive(int n)
  6.         {
  7.                 int u1, u2, f;
  9.                 if (n < 2)
  10.                         f = n + 1;
  11.                 else {
  12.                         u1 = f_recursive((int)(n/2));
  13.                         u2 = f_recursive((int)(n/4));
  14.                         f = u1 * u2;                                                                                         
  15.                 }
  17.                 return f;
  18.         }
复制代码

       
           下面按照我们上面说的,确定好递归调用树的结构,这一步是最重要的.首先,什么是叶子结点
        ,我们看到当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))就分别是左子树和右子
        树了.{zh1},我们可以看到,这个递归函数可以表示成后序遍历的二叉调用树.好了,树的情况分析
        到这里,下面来分析一下栈的情况,看看我们要把什么数据保存在栈中,在上面给出的后序遍历的如果这个过程你没
        非递归程序中我们已经看到了要加入一个标志域,因此在栈中要保存这个标志域;另外,u1,u2和
        每次调用递归函数时的n/2和n/4参数都要保存,这样就要分别有三个栈分别保存:标志域,返回量
        和参数,不过我们可以做一个优化,因为在向上一层返回的时候,参数已经没有用了,而返回量也
        只有在向上返回时才用到,因此可以把这两个栈合为一个栈.如果对于上面的分析你没有明白,建
        议你根据这个递归函数写出它的递归栈的变化情况以加深理解,再次重申一点:前期对树结构和
        栈的分析是最重要的,如果你的程序出错,那么请返回到这一步来再次分析,{zh0}把递归调用树和
        栈的变化情况都画出来,并且结合一些简单的参数来人工分析你的算法到底出错在哪里.
            ok,下面给出我花了两天功夫想出来的非递归程序(再次提醒你不要气馁,大家都是这么过来
        的).
       
  1. int        f_nonrecursive(int n)
  2.         {
  3.                 int stack[20], flag[20], cp;
  4.                                                  
  5.                 /* 初始化栈和栈顶指针 */
  6.                 cp = 0;
  7.                 stack[0] = n;
  8.                 flag[0] = 0;
  10.                 while (cp >;= 0) {
  11.                         switch(flag[cp]) {
  12.                         case 0:                         /* 访问的是根结点 */
  13.                                 if (stack[cp] >;= 2) {        /* 左子树入栈 */
  14.                                         flag[cp] = 1;         /* 修改标志域 */
  15.                                         cp++;
  16.                                         stack[cp] = (int)(stack[cp - 1] / 2);
  17.                                         flag[cp] = 0;
  18.                                 } else {                 /* 否则为叶子结点 */
  19.                                         stack[cp] += 1;
  20.                                         flag[cp] = 2;
  21.                                 }
  22.                                 break;
  23.                         case 1:                         /* 访问的是左子树 */
  24.                                 if (stack[cp] >;= 2) {        /* 右子树入栈 */
  25.                                         flag[cp] = 2;         /* 修改标志域 */
  26.                                         cp += 2;
  27.                                         stack[cp] = (int)(stack[cp - 2] / 4);
  28.                                         flag[cp] = 1;
  29.                                 } else {                 /* 否则为叶子结点 */
  30.                                         stack[cp] += 1;
  31.                                         flag[cp] = 2;
  32.                                 }
  33.                                 break;
  34.                         case 2:                                 /* */
  35.                                 if (flag[cp - 1] == 2) { /* 当前是右子树吗? */
  36.                                         /*
  37.                                          * 如果是右子树, 那么对某一棵子树的后序遍历已经
  38.                                          * 结束,接下来就是对这棵子树的根结点的访问
  39.                                          */
  40.                                         stack[cp - 2] = stack[cp] * stack[cp - 1];
  41.                                         flag[cp - 2] = 2;
  42.                                         cp = cp - 2;
  43.                                 } else
  44.                                         /* 否则退回到后序遍历的上一个结点 */
  45.                                         cp--;
  46.                                 break;
  47.                         }
  48.                 }
  50.                 return stack[0];
  51.         }
复制代码

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

        2)例子二
       
        快速排序算法
        递归算法如下:
       
  1. void        swap(int array[], int low, int high)
  2.         {
  3.                 int temp;
  5.                 temp = array[low];
  6.                 array[low] = array[high];
  7.                 array[high] = temp;
  8.         }
  10.         int        partition(int array[], int low, int high)
  11.         {
  12.                 int        p;
  14.                 p = array[low];
  16.                 while (low < high) {
  17.                         while (low < high && array[high] >;= p)
  18.                                 high--;
  19.                         swap(array,low,high);
  20.                         while (low < high && array[low]  <= p)
  21.                                 low++;
  22.                         swap(array,low,high);
  23.                 }
  25.                 return low;
  26.         }
  28.         void        qsort_recursive(int array[], int low, int high)
  29.         {
  30.                 int p;
  32.                 if(low < high) {
  33.                         p = partition(array, low, high);
  34.                         qsort_recursive(array, low, p - 1);
  35.                         qsort_recursive(array, p + 1, high);
  36.                 }
  37.         }
复制代码

           需要说明一下快速排序的算法: partition函数根据数组中的某一个数把数组划分为两个部分,
        左边的部分均不大于这个数,右边的数均不小于这个数,然后再对左右两边的数组再进行划分.这
        里我们专注于递归与非递归的转换,partition函数在非递归函数中同样的可以调用(其实
        partition函数就是对当前结点的访问).
           再次进行递归调用树和栈的分析:
           递归调用树:a)对当前结点的访问是调用partition函数;b)左子树:
        qsort_recursive(array, low, p - 1);c)右子树:qsort_recursive(array, p + 1, high);
        d)叶子结点:当low < high时;e)可以看出这是一个先序调用的二叉树
           栈:要保存的数据是两个表示范围的坐标.
          
  1. void        qsort_nonrecursive(int array[], int low, int high)
  2.         {
  3.                 int m[50], n[50], cp, p;
  5.                 /* 初始化栈和栈顶指针 */
  6.                 cp = 0;
  7.                 m[0] = low;
  8.                 n[0] = high;
  10.                 while (m[cp] < n[cp]) {
  11.                         while (m[cp] < n[cp]) {        /* 向左走到尽头 */
  12.                                 p = partition(array, m[cp], n[cp]); /* 对当前结点的访问 */
  13.                                 cp++;
  14.                                 m[cp] = m[cp - 1];
  15.                                 n[cp] = p - 1;
  16.                         }
  17.                         /* 向右走一步 */
  18.                         m[cp + 1] = n[cp] + 2;
  19.                         n[cp + 1] = n[cp - 1];
  20.                         cp++;
  21.                 }
  22.         }
复制代码

       
        3)例子三
        阿克曼函数:
  1. akm(m, n) = n + 1;                        (m = 0时)
  2.                     akm(m - 1, 1);                (n = 0时)
  3.                     akm(m - 1, akm(m, n - 1));        (m != 0且n != 0时)
复制代码
            

        递归算法如下:
       
  1. int        akm_recursive(int m, int n)
  2.         {
  3.                 int temp;
  5.                 if (m == 0)
  6.                         return (n + 1);
  7.                 else if (n == 0)
  8.                         return akm_recursive(m - 1, 1);
  9.                 else {
  10.                         temp = akm_recursive(m, n - 1);
  11.                         return akm_recursive(m - 1, temp);
  12.                 }
  13.         }
复制代码


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

posted on 2010-04-27 00:22 阅读(1)  

郑重声明：资讯 【如何用栈实现递归与非递归的转换(转) - 网络工程3班- 博客园】由 发布，版权归原作者及其所在单位，其原创性以及文中陈述文字和内容未经(企业库qiyeku.com)证实，请读者仅作参考，并请自行核实相关内容。若本文有侵犯到您的版权， 请你提供相关证明及申请并与我们联系（qiyeku # qq.com）或【在线投诉】，我们审核后将会尽快处理。
—— 相关资讯 ——
广西防火窗生产厂家欧普达门业
广西防火窗生产厂家欧普达门业
2018/8/18
热烈祝贺我公司被评为玉林市科技创新中小企业
热烈祝贺我公司被评为玉林市科技创新中小企业
2016/9/25
【广-州】黄埔哪家医院做包皮手术{zh0}
【广-州】黄埔哪家医院做包皮手术{zh0}
2015/11/25
选购耐根穿刺防水卷材认准钰强防水——生产耐根穿刺防水卷材
选购耐根穿刺防水卷材认准钰强防水——生产耐根穿刺防水卷材
2016/5/20
长乐食品包装袋_泉州优质的食品包装袋市场价格
长乐食品包装袋_泉州优质的食品包装袋市场价格
1900/1/1
笔记本内存2G还是4G？内存升级前后性能对比测试_洫殺АΚ _百度空间
笔记本内存2G还是4G？内存升级前后性能对比测试_洫殺АΚ _百度空间
2010/3/14
各位版主什么时候能够开展一下各版块的定期活动！|意见申诉- 红军长征 ...
各位版主什么时候能够开展一下各版块的定期活动！|意见申诉- 红军长征 ...
2010/3/17
六因素决定我国农机市场面临更好机遇- 如虎添e - 飞行者WFXY - 和讯博客
六因素决定我国农机市场面临更好机遇- 如虎添e - 飞行者WFXY - 和讯博客
2010/5/4
JDB-YE+Z30电动机保护器,JDB-YE+Z30接线图阿里巴巴huayi123123的博客BLOG
JDB-YE+Z30电动机保护器,JDB-YE+Z30接线图阿里巴巴huayi123123的博客BLOG
2010/5/17
国产温度仪表-KWN-1TA 温度控制器|-三达牌温度调节器« 电力仪表制造商 ...
国产温度仪表-KWN-1TA 温度控制器|-三达牌温度调节器« 电力仪表制造商 ...
2010/6/6
耐高温310S不锈钢圆钢0Cr25Ni20不锈钢圆钢022-26399665 | 【娱乐灌水 ...
耐高温310S不锈钢圆钢0Cr25Ni20不锈钢圆钢022-26399665 | 【娱乐灌水 ...
2010/6/26
【怎样订购红酒木瓜靓汤】-知名xxxxxx：怎样订购红酒木瓜靓汤
【怎样订购红酒木瓜靓汤】-知名xxxxxx：怎样订购红酒木瓜靓汤
2013/3/16
什么去黑眼圈产品最快
什么去黑眼圈产品最快
2015/3/2
挂什么画招财人气旺 国画花鸟画更受欢迎
挂什么画招财人气旺 国画花鸟画更受欢迎
2015/3/11