精华内容
下载资源
问答
  • 前面在Topcoder上面看到一道题,是用到递归,于是说仔细学习一下递归算法,想到汉诺塔应该是最入门递归,结果折腾了半天写出来 。最后去找了个正确答案。最后虽然似乎看懂了,但自问个人真是写出来。所以就贴...



    前面在Topcoder上面看到一道题,是用到递归,于是说仔细学习一下递归算法,想到汉诺塔应该是最入门的递归,结果折腾了半天写不出来 。最后去找了个正确答案。最后虽然似乎看懂了,但自问个人真是写不出来。所以就贴在这里,算是对自己的一种鞭策吧!


    def hanoi(n,list_from, list_to=[], list_buf=[]):
        global count
        if n > 0:
            hanoi(n -1 ,list_from,list_buf,list_to)
            if list_from:
                list_to.append(list_from.pop())
                print list_from, list_to, list_buf
                count += 1
            hanoi(n -1, list_buf,list_to,list_from)
    count = 0        
    list1 = range(4,0,-1)
    list_to = []
    hanoi(4,list1, list_to)
    print list_to, count


    展开全文
  • 递归与非递归转换基础知识是能够正确理解三种树遍历方法:前序,中序和后序,第一篇就是关于这三种遍历方法递归和非递归算法。 如何用栈实现递归与非递归转换(一)三种遍历树算法 一.为什么要...
    递归与非递归转换的基础知识是能够正确理解三种树的遍历方法:前序,中序和后序,第一篇就是关于这三种遍历方法的递归和非递归算法。
    


    如何用栈实现递归与非递归的转换(一)三种遍历树的算法

    一.为什么要学习递归与非递归的转换的实现方法? 
    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.ptr,2});    /* 修改mark域 */ 
                                     if(a.ptr->rchild) 
                                        push(S,{a.ptr->rchild,0}); /* 访问右子树 */ 
                                     break; 
                                  case 2: 
                                     visit(a.ptr);       /* 访问结点 */ 
                                  } 
                               } 
                            }

    展开全文
  • 1、理解递归,关键是脑中有一幅代码图片,函数执行到递归函数入口时,就扩充一段完全一样代码,执行完扩充代码并return后,继续执行前一次递归函数中递归函数入口后面代码),阅读...2、递归算法的设计:(1)递...

    1、理解递归,关键是脑中有一幅代码的图片,函数执行到递归函数入口时,就扩充一段完全一样的代码,执行完扩充的代码并return后,继续执行前一次递归函数中递归函数入口后面的代码),阅读递归函数最容易的方法不是纠缠于它的执行过程,而是相信递归函数会顺利完成它的任务。如果你的每个步骤正确无误,你的限制条件设置正确,并且每次调用之后更接近限制条件,递归函数总是能正确的完成任务。

    2、递归算法的设计:

    (1)递归模型是递归问题的本质

    (2)使用递归树描述向下分解与向上求值的过程

    展开全文
  • 递归 VS 非递归 内涵

    2019-10-06 14:49:02
    递归与非递归转换基础知识是能够正确理解三种树遍历方法:前序,中序和后序,第一篇就是关于这三种遍历方法递归和非递归算法。 一、为什么要学习递归与非递归转换实现方法? 1)并是每一门语言都支持...

    递归与非递归转换的基础知识是能够正确理解三种树的遍历方法:前序,中序和后序,第一篇就是关于这三种遍历方法的递归和非递归算法。

    一、为什么要学习递归与非递归的转换的实现方法?

    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 + 1;   (n <2)

                         = f[n/2] + f[n/4](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 < 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,下面给出我花了两天功夫想出来的非递归程序(再次提醒你不要气馁,大家都是这么过来的)。

    代码:

    int        f_nonrecursive(int n)    

           {    

                  int    stack[20],    flag[20],cp;                   

                  /* 初始化栈和栈顶指针      */

                  cp = 0;   

                  stack[0] = n;  

                  flag[0]     =     0;

                  while       (cp >= 0)      {    

                         switch(flag[cp]) {

                                case 0:                                /* 访问的是根结点      */

                                       if (stack[cp]   >= 2)      {            /* 左子树入栈      */

                                              flag[cp] = 1;          /*   修改标志域 */     

                                              cp++;     

                                              stack[cp] =     (int)(stack[cp - 1] /      2);  

                                              flag[cp] = 0;  

                                       }     else {                    /*   否则为叶子结点 */     

                                              stack[cp] += 1;     

                                              flag[cp] = 2;  

                                       }    

                                       break;

                                case 1:                                /* 访问的是左子树      */

                                       if (stack[cp]   >= 2)      {            /* 右子树入栈      */

                                              flag[cp] = 2;          /*   修改标志域 */     

                                              cp +=      2;

                                              stack[cp] =     (int)(stack[cp - 2] /      4);  

                                              flag[cp] = 1;  

                                       }     else {                    /*   否则为叶子结点 */     

                                              stack[cp] += 1;     

                                              flag[cp] = 2;  

                                       }    

                                       break;

                                case 2:                                       /*   */

                                       if (flag[cp       -      1] ==      2) { /*     当前是右子树吗? */

                                              /* * 如果是右子树,  

                                              那么对某一棵子树的后序遍历已经    *    

                                              结束,接下来就是对这棵子树的根结点的访问      

                                              */

                                              stack[cp-2] = stack[cp] * stack[cp      -1];

                                              flag[cp - 2]     =     2;

                                              cp    =     cp - 2;    

                                              }     else

                                       /*    否则退回到后序遍历的上一个结点 */     

                                                     cp--;

                                                     break;

                  }

           }    

           return stack[0];

    }

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

    2)例2:

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

    void   swap(int array[], int low, int high)

    {

           int temp;

           temp = array[low];

           array[low] = array[high];

           array[high] = temp;

    }

    int   partition(int array[], int low, int high)

    {

          int   p;

          p = array[low];

          while (low < high) {

               while (low < high && array[high] >= p)

                        high--;

               swap(array,low,high);

               while (low < high && array[low] <= 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 m[50], n[50], cp, p;

           cp = 0; m[0] = low; n[0] = high; /* 初始化栈和栈顶指针 */       

           while (m[cp] < n[cp]) {

                while (m[cp] < n[cp]) {   /* 向左走到尽头 */

                       p = partition(array, m[cp], n[cp]); /* 对当前结点的访问 */

                       cp++;

                       m[cp] = m[cp - 1];

                       n[cp] = p - 1;

                }

                /* 向右走一步 */

                m[cp + 1] = n[cp] + 2;

                n[cp + 1] = n[cp - 1];

                cp++;

           }

    }

    四、递归程序的分类及用途

        递归程序分为两类:尾部递归和非尾部递归。上面提到的几个例子都是非尾部递归,在一个选择分支中有至少一个的递归调用。相对而言,尾部递归就容易很多了,因为与非尾部递归相比,每个选择分支只有一个递归调用,

    我们在解决的时候就不需要使用到栈,只要循环和设置好循环体就可以了。下面再举几个尾部递归的例子吧,比较简单我就不多说什么了。

    1)例1:

    g(m, n) = 0 (m = 0, n >= 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)栈,非尾部调用中需要栈来保存数据,这一点已经很清楚了,需要注意几个问题:a)栈有时可能会出现不够的情况,拿上面的akm函数来说,我用的50个 元素的数组,你如果把m和n值设置得大一些,这个栈就不能用了,有时你的算法正确了,不过没有注意到这个问题还是会出错的;反过来说,在递归调用中,系统 或者编译器的优化功能不够好的化,在这个栈上可能会消耗很多空间,这个时候如果你把程序改成非递归的形式,然后再用动态分配技术分配栈可能就会把程序的性 能提高一大块--这也是我们学习这门技术的意义之一,因为系统是机械化的,你如果知道更好的优化办法,为什么不用呢?

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

        说白了,递归程序是在对所要解决的问题进行数学上的分析后给出的,也就是说递归算法是从纯数学的角度出 发考虑的,而非递归的算法则是在递归算法的基础上考虑计算机内部处理递归程序的机制考虑来实现转换的。任何一个递归算法,只要能够准确的写出递归调用树的 情况,分析清楚对当前结点的访问操作是什么,左子树右子树是什么那么实现起递归和非递归的转换就很轻松了。

    转载于:https://www.cnblogs.com/SuperXJ/archive/2010/09/26/1836155.html

    展开全文
  • 递归VS非递归

    2012-05-13 23:23:11
    递归与非递归转换基础知识是能够正确理解三种树遍历方法:前序,中序和后序,第一篇就是关于这三种遍历方法递归和非递归算法。 一、为什么要学习递归与非递归转换实现方法? 1)并是每一门语言都支持...
  • 如何用栈实现递归与非递归的转换

    千次阅读 2006-06-30 11:48:00
    递归与非递归转换基础知识是能够正确理解三种树遍历方法:前序,中序和后序,第一篇就是关于这三种遍历方法递归和非递归算法。一、为什么要学习递归与非递归转换实现方法? 1)并是每一门语言都支持递归...
  • 递归与非递归转换

    千次阅读 2009-11-26 10:15:00
    递归与非递归转换基础知识是能够正确理解三种树遍历方法:前序,中序和后序,第一篇就是关于这三种遍历方法递归和非递归算法。一、为什么要学习递归与非递归转换实现方法? 1)并是每一门语言都支持递归...
  • 快速排序算法思想:快速排序是找出一个元素(理论上可以随便找一个)作为基准(pivot),然后对数组进行分区操作,使基准左边元素值都大于基准值,基准右边元素值都小于基准值,如此作为基准元素调整到排序后...
  • http://null.bokee.com/209747.html<br />(一)三种遍历树算法  递归与非递归转换基础知识是能够正确理解三种树遍历方法:前序,中序和后序,第一篇就是关于这三种遍历方法递归和非递归算法。...
  • 三种遍历算法

    2014-10-03 11:16:11
    递归与非递归转换基础知识是能够正确理解三种树遍历方法:前序,中序和后序,第一篇就是关于这三种遍历方法递归和非递归算法。 如何用栈实现递归与非递归转换(一)三种遍历树算法 一.为什么要...
  • 三种遍历树的算法

    2014-07-10 09:20:47
    递归与非递归转换基础知识是能够正确理解三种树遍历方法:前序,中序和后序,第一篇就是关于这三种遍历方法递归和非递归算法。 如何用栈实现递归与非递归转换(一)三种遍历树算法 一.为什么要...
  • 这阵子在认真地看着算法导论,之前看到第四章计算分治法时间复杂度计算方法被称为“主方法”,运用这个主方法可以快速地口算出分治算法的递归时间复杂度,以下给出算法导论里关于主方法描述吧,我就直接...
  • 算法主公式

    2020-07-03 00:10:50
    这阵子在认真地看着算法导论,之前看到第四章计算分治法时间复杂度计算方法被称为“主方法”,运用这个主方法可以快速地口算出分治算法的递归时间复杂度,以下给出算法导论里关于主方法描述吧,我就直接...
  • 甚至有些问题在递归算法下导致内存和程序崩溃,就是因为计算太慢了,这时我们可以用迭代算法,虽然之前讲过递归算法比迭代更有效率,但是在某些问题情况下,迭代算法是比递归更加有效容易导致崩溃!...
  • > 设计一个递归算法,删除带头结点的单链表L中所有值为x的结点。 答案给的是C++代码,使用了引用&: ![图片说明](https://img-ask.csdn.net/upload/202006/05/1591342008_651545.jpg) 因为我用的是C语言,...
  • 任何数学递推公式都可以直接转换为递归算法,但是基本现实是编译器常常正确对待递归算法,结果导致低效程序。当怀疑出现这样情况时,我们必须再给编译器提供一些帮助,即将递归算法转换为非递归算法,让后者...
  • 关于动态规划一点总结

    多人点赞 2011-09-01 09:46:24
    动态规划基本思想是,将原问题分解为相似子问题,在求解...任何递推公式都可以直接翻译成递归算法,但是基本实现时编译器往往正确对待递归算法,结果产生低效程序,当怀疑是这种情况时,必须给编译器一些帮助
  • Java数据结构与算法相关题 1.栈是一种按“后进先出“,原则进行插入和删除操作的数据结构,因此( A ) 必须用栈。 A、实现函数或过程的递归调用...3.下列关于栈的叙述正确的是( D ) A、栈是非线性结构 B、栈是一种树状
  • 本文是一个汉诺塔递归算法,但是我疑问为什么最大只能够输入31?超过就显示正确执行程序? #include using namespace std; //圆盘个数最多为64 const int MAX=64; //用来表示每根柱子信息 ...
  • 任何数学递归公式可以直接翻译成递归算法,但是基本现实是编译器常常正确对待递归算法,结果导致低效算法。当我们怀疑很可能是这种情况时,我们必须给编译器一些帮助,将递归算法重新写成非递归算法,让后者把...
  • (转)树遍历

    2015-03-13 10:41:00
    递归与非递归转换基础知识是能够正确理解三种树遍历方法:前序,中序和后序,第一篇就是关于这三种遍历方法递归和非递归算法。 如何用栈实现递归与非递归转换(一)三种遍历树算法 一.为什么要学习...
  • 遍历树

    2013-11-22 23:24:09
    递归与非递归转换基础知识是能够正确理解三种树遍历方法:前序,中序和后序,第一篇就是关于这三种遍历方法递归和非递归算法。 如何用栈实现递归与非递归转换(一)三种遍历树算法 一.为什么要...
  • visit_tree

    2014-06-01 16:42:48
    递归与非递归转换基础知识是能够正确理解三种树遍历方法:前序,中序和后序,第一篇就是关于这三种遍历方法递归和非递归算法。 如何用栈实现递归与非递归转换(一)三种遍历树算法 一.为什么要学习递归与...
  • 动态规划

    2015-05-21 14:57:13
    但常常编译器正确对待递归算法,导致低效算法。我们将递归算法重新写成非递归算法,让后者把那些子问题答案系统地记录在一个表内。利用这种方法一种技巧叫做动态规划(dynamic programming) 。动态规划一般...
  • 关于嵌入式性能调优

    2008-10-01 23:18:00
    本来对嵌入式性能调优方面的一些文章还有些不以为然,但经过自己亲身体验之后,我不得承认那些都是无比正确的。 对于性能问题,我一向的观点是,首先优化算法,能够查表的情况下就查表(如三角函数),能展开写的...
  • C#数据结构

    2013-12-10 11:49:54
    刚学程序设计时,常听人说程序设计水平要想提高,最重要的是多看别人写的程 序,多去思考问题。从别人写的程序中,我们可以发现效率更高的解决方法;从 思考问题的过程中,我们可以了解解决问题的方法常常不只一个。...

空空如也

空空如也

1 2 3
收藏数 58
精华内容 23
关键字:

关于递归算法不正确的是