信息与计算科学专业毕业论文算法设计中的递归与非递归转换

《信息与计算科学专业毕业论文算法设计中的递归与非递归转换》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、摘要算法设计中的递归和非递归转换是学习算法设计的基础，熟练地运用递归与非递归转换是算法设计的基础，在这篇论文中我就介绍几种算法设计中的递归与非递归的转换方法.让大家可以更好的实现算法设计中的递归和非递归转换。关键词：算法设计递归与非递归转换AbstractThealgorithmdesignrecursiveandnonrecursiveconversionisthebasisforlearningalgorithmdesign,skilleduseofrecursiveandnonrecursiveconversionisthebasisforalgorithmdesignint

2、hispaperIwillintroduceseveralalgorithmdesignrecursiveandnonrecursiveconversionmethod.sothatwecanbetterachievetherecursivealgorithmdesignandnon-recursiveconversion.Keywords:algorithmdesignrecursiveandnonrecursiveconversion三种遍历树的算法    递归与非递归转换的基础知识是能够正确理解三种树的遍历方法：前序，中序和后序，第一篇就是关于这三种遍历方法的递归和非递归算法

3、。一、为什么要学习递归与非递归的转换的实现方法    1.并不是每一门语言都支持递归的.    2.有助于理解递归的本质.    3.有助于理解栈,树等数据结构.二、三种遍历树的递归和非递归算法    递归与非递归的转换基于以下的原理:所有的递归程序都可以用树结构表示出来.需要说明的是,这个"原理"并没有经过严格的数学证明,只是我的一个猜想,不过在至少在我遇到的例子中是适用的.学习过树结构的人都知道,有三种方法可以遍历树:前序,中序,后序.理解这三种遍历方式的递归和非递归的表达方式是能够正确实现转换的关键之处,所以我们先来谈谈这个.需要说明的是,这里以特殊的二叉树来说明,不过大多数

4、情况下二叉树已经够用,而且理解了二叉树的遍历,其它的树遍历方式就不难了。        1)前序遍历        a)递归方式:              voidpreorder_recursive(BitreeT)     /*先序遍历二叉树的递归算法*/                    {                       if(T){                          visit(T);         /*访问当前结点*/                          preorder_recursive(T->lchild);  /

5、*访问左子树*/                          preorder_recursive(T->rchild);  /*访问右子树*/                       }                    }        b)非递归方式              voidpreorder_nonrecursive(BitreeT)     /*先序遍历二叉树的非递归算法*/                    {                       initstack(S);                       push(S,T)

6、;            /*根指针进栈*/                       while(!stackempty(S)){                          while(gettop(S,p)&&p){     /*向左走到尽头*/                             visit(p);     /*每向前走一步都访问当前结点*/                             push(S,p->lchild);                          }                          pop(

7、S,p);                          if(!stackempty(S)){     /*向右走一步*/                             pop(S,p);                             push(S,p->rchild);                          }                       }                    }        2)中序遍历