递归算法工作栈的变化详解

《递归算法工作栈的变化详解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

通常,一个函数在调用另一个函数之前,要作如下的事情:a)将实在参数,返回地址等信息传递给被调用函数保存;b)为被调用函数的局部变量分配存储区;c)将控制转移到被调函数的入口.   从被调用函数返回调用函数之前,也要做三件事情:a)保存被调函数的计算结果;b)释放被调函数的数据区;c)依照被调函数保存的返回地址将控制转移到调用函数.所有的这些,不论是变量还是地址,本质上来说都是"数据",都是保存在系统所分配的栈中的.   ok,到这里已经解决了第一个问题:递归调用时数据都是保存在栈中的,有多少个数据需要保存就要设置多少个栈,而且最重要的一点是:控制所有这些栈的栈顶指针都是相同的,否则无法实现同步.   下面来解决第二个问题:在非递归中,程序如何知道到底要转移到哪个部分继续执行?回到上面说的树的三种遍历方式,抽象出来只有三种操作:访问当前结点,访问左子树,访问右子树.这三种操作的顺序不同,遍历方式也不同.如果我们再抽象一点,对这三种操作再进行一个概括,可以得到:a)访问当前结点:对目前的数据进行一些处理;b)访问左子树:变换当前的数据以进行下一次处理;c)访问右子树:再次变换当前的数据以进行下一次处理(与访问左子树所不同的方式).   下面以先序遍历来说明:   voidpreorder_recursive(BitreeT)     /*先序遍历二叉树的递归算法*/   {                       if(T){                          visit(T);         /*访问当前结点*/                          preorder_recursive(T->lchild);  /*访问左子树*/                          preorder_recursive(T->rchild);  /*访问右子树*/                       }                    }   visit(T)这个操作就是对当前数据进行的处理,preorder_recursive(T->lchild)就是把当前数据变换为它的左子树,访问右子树的操作可以同样理解了.   现在回到我们提出的第二个问题:如何确定转移到哪里继续执行?关键在于一下三个地方:a)确定对当前数据的访问顺序,简单一点说就是确定这个递归程序可以转换为哪种方式遍历的树结构;b)确定这个递归函数转换为递归调用树时的分支是如何划分的,即确定什么是这个递归调用树的"左子树"和"右子树"c)确定这个递归调用树何时返回,即确定什么结点是这个递归调用树的"叶子结点". 二）.三个例子   好了上面的理论知识已经足够了,下面让我们看看几个例子,结合例子加深我们对问题的认识.即使上面的理论你没有完全明白,不要气馁,对事物的认识总是曲折的,多看多想你一定可以明白(事实上我也是花了两个星期的时间才弄得比较明白得).  1)例子一: f(n)=n+１;  (n<２)                    =f[n/2]+f[n/4](n>=2);                      这个例子相对简单一些,递归程序如下:                    int  f_recursive(intn)                    {intu1,u2,f;                       if(n<2)                          f=n+1;                       else{                          u1=f_recursive((int)(n/2)); u2=f_recursive((int)(n/4));                          f=u1*u2;                                                        }                       returnf;}   下面按照我们上面说的,确定好递归调用树的结构,这一步是最重要的.首先,什么是叶子结点,我们看到当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(intn)                    {                       intstack[20],flag[20],cp;                                                           /*初始化栈和栈顶指针*/                       cp=0;                       stack[0]=n;                       flag[0]=0;                       while(cp>=0){                          switch(flag[cp]){                          case0:         /*访问的是根结点*/                             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;                          case1:         /*访问的是左子树*/                             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;                          case2:            /**/                             if(flag[cp-1]==2){/*当前是右子树吗?*/                                /*                                 *如果是右子树,那么对某一棵子树的后序遍历已经                                 *结束,接下来就是对这棵子树的根结点的访问                                 */                                stack[cp-2]=stack[cp]*stack[cp-1];                                flag[cp-2]=2;                                cp=cp-2;                             }else                                /*否则退回到后序遍历的上一个结点*/                                cp--;                             break;}}                       returnstack[0];}   算法分析:a)flag只有三个可能值:0表示第一次访问该结点,1表示访问的是左子树,2表示已经结束了对某一棵子树的访问,可能当前结点是这棵子树的右子树,也可能是叶子结点.b)每遍历到某个结点的时候,如果这个结点满足叶子结点的条件,那么把它的flag域设为2;否则根据访问的是根结点,左子树或是右子树来设置flag域,以便决定下一次访问该节点时的程序转向.           2)例子二            快速排序算法           递归算法如下:                 代码:                 void  swap(intarray[],intlow,inthigh)                    {inttemp;                       temp=array[low];                       array[low]=array[high];                       array[high]=temp;}                    int  partition(intarray[],intlow,inthigh)                    {                       int  p;                       p=array[low];                       while(low=p)                             high--;                          swap(array,low,high);                          while(low0){      /*压栈,直到m1[cp]=0*/                             while(n1[cp]>0){   /*压栈,直到n1[cp]=0*/                                cp++;                                m1[cp]=m1[cp-1];                                n1[cp]=n1[cp-1]-1;}                             /*计算akm(m-1,1),当n=0时*/                             m1[cp]=m1[cp]-1;                             n1[cp]=1;                          }                          /*改栈顶为akm(m-1,n+1),当m=0时*/                          cp--;                          m1[cp]=m1[cp]-1;n1[cp]=n1[cp+1]+1;                       }while(cp>0||m1[cp]>0);                       returnn1[0]+1;                    }    递归算法详解C通过运行时堆栈支持递归函数的实现。递归函数就是直接或间接调用自身的函数。    许多教科书都把计算机阶乘和菲波那契数列用来说明递归，非常不幸我们可爱的著名的老潭老师的《C语言程序设计》一书中就是从阶乘的计算开始的函数递归。导致读过这本经书的同学们，看到阶乘计算第一个想法就是递归。但是在阶乘的计算里，递归并没有提供任何优越之处。在菲波那契数列中，它的效率更是低的非常恐怖。    这里有一个简单的程序，可用于说明递归。程序的目的是把一个整数从二进制形式转换为可打印的字符形式。例如：给出一个值4267，我们需要依次产生字符‘4’，‘2’，‘6’，和‘7’。就如在printf函数中使用了%d格式码，它就会执行类似处理。     我们采用的策略是把这个值反复除以10，并打印各个余数。例如，4267除10的余数是7，但是我们不能直接打印这个余数。我们需要打印的是机器字符集中表示数字‘7’的值。在ASCII码中，字符‘7’的值是55，所以我们需要在余数上加上48来获得正确的字符，但是，使用字符常量而不是整型常量可以提高程序的可移植性。‘0’的ASCII码是48，所以我们用余数加上‘0’，所以有下面的关系：         ‘0’+0=‘0’        ‘0’+1=‘1’        ‘0’+2=‘2’    　　　  ...　　从这些关系中，我们很容易看出在余数上加上‘0’就可以产生对应字符的代码。接着就打印出余数。下一步再取商的值，4267/10等于426。然后用这个值重复上述步骤。　　这种处理方法存在的唯一问题是它产生的数字次序正好相反，它们是逆向打印的。所以在我们的程序中使用递归来修正这个问题。　　我们这个程序中的函数是递归性质的,因为它包含了一个对自身的调用。乍一看，函数似乎永远不会终止。当函数调用时，它将调用自身，第2次调用还将调用自身，以此类推，似乎永远调用下去。这也是我们在刚接触递归时最想不明白的事情。但是，事实上并不会出现这种情况。　　这个程序的递归实现了某种类型的螺旋状while循环。while循环在循环体每次执行时必须取得某种进展，逐步迫近循环终止条件。递归函数也是如此，它在每次递归调用后必须越来越接近某种限制条件。当递归函数符合这个限制条件时，它便不在调用自身。在程序中，递归函数的限制条件就是变量quotient为零。在每次递归调用之前，我们都把quotient除以10，所以每递归调用一次，它的值就越来越接近零。当它最终变成零时，递归便告终止。/*接受一个整型值（无符号0，把它转换为字符并打印它，前导零被删除*/#includeintbinary_to_ascii(unsignedintvalue){        unsignedintquotient;    　　quotient=value/10;  　　if(quotient!=0)     　　　　binary_to_ascii( quotient);  　　putchar(value%10+'0');}递归是如何帮助我们以正确的顺序打印这些字符呢？下面是这个函数的工作流程。      1.将参数值除以10      2.如果quotient的值为非零，调用binary-to-ascii打印quotient当前值的各位数字　　3.接着，打印步骤1中除法运算的余数　　注意在第2个步骤中，我们需要打印的是quotient当前值的各位数字。我们所面临的问题和最初的问题完全相同，只是变量quotient的值变小了。我们用刚刚编写的函数（把整数转换为各个数字字符并打印出来）来解决这个问题。由于quotient的值越来越小，所以递归最终会终止。　　一旦你理解了递归，阅读递归函数最容易的方法不是纠缠于它的执行过程，而是相信递归函数会顺利完成它的任务。如果你的每个步骤正确无误，你的限制条件设置正确，并且每次调用之后更接近限制条件，递归函数总是能正确的完成任务。　　但是，为了理解递归的工作原理，你需要追踪递归调用的执行过程，所以让我们来进行这项工作。追踪一个递归函数的执行过程的关键是理解函数中所声明的变量是如何存储的。当函数被调用时，它的变量的空间是创建于运行时堆栈上的。以前调用的函数的变量扔保留在堆栈上，但他们被新函数的变量所掩盖，因此是不能被访问的。　　当递归函数调用自身时，情况于是如此。每进行一次新的调用，都将创建一批变量，他们将掩盖递归函数前一次调用所创建的变量。当我追踪一个递归函数的执行过程时，必须把分数不同次调用的变量区分开来，以避免混淆。　　程序中的函数有两个变量：参数value和局部变量quotient。下面的一些图显示了堆栈的状态，当前可以访问的变量位于栈顶。所有其他调用的变量饰以灰色的阴影，表示他们不能被当前正在执行的函数访问。假定我们以4267这个值调用递归函数。当函数刚开始执行时，堆栈的内容如下图所示： 执行除法之后，堆栈的内容如下：接着，if语句判断出quotient的值非零，所以对该函数执行递归调用。当这个函数第二次被调用之初，堆栈的内容如下：堆栈上创建了一批新的变量，隐藏了前面的那批变量，除非当前这次递归调用返回，否则他们是不能被访问的。再次执行除法运算之后，堆栈的内容如下：quotient的值现在为42，仍然非零，所以需要继续执行递归调用，并再创建一批变量。在执行完这次调用的出发运算之后，堆栈的内容如下： 此时，quotient的值还是非零，仍然需要执行递归调用。在执行除法运算之后，堆栈的内容如下：　　不算递归调用语句本身，到目前为止所执行的语句只是除法运算以及对quotient的值进行测试。由于递归调用这些语句重复执行，所以它的效果类似循环：当quotient的值非零时，把它的值作为初始值重新开始循环。但是，递归调用将会保存一些信息（这点与循环不同），也就好是保存在堆栈中的变量值。这些信息很快就会变得非常重要。　　现在quotient的值变成了零，递归函数便不再调用自身，而是开始打印输出。然后函数返回，并开始销毁堆栈上的变量值。每次调用putchar得到变量value的最后一个数字，方法是对value进行模10取余运算，其结果是一个0到9之间的整数。把它与字符常量‘0’相加，其结果便是对应于这个数字的ASCII字符，然后把这个字符打印出来。  输出4： 接着函数返回，它的变量从堆栈中销毁。接着，递归函数的前一次调用重新继续执行，她所使用的是自己的变量，他们现在位于堆栈的顶部。因为它的value值是42，所以调用putchar后打印出来的数字是2。输出42：接着递归函数的这次调用也返回，它的变量也被销毁，此时位于堆栈顶部的是递归函数再前一次调用的变量。递归调用从这个位置继续执行，这次打印的数字是6。在这次调用返回之前，堆栈的内容如下：输出426： 现在我们已经展开了整个递归过程，并回到该函数最初的调用。这次调用打印出数字7，也就是它的value参数除10的余数。输出4267：然后，这个递归函数就彻底返回到其他函数调用它的地点。如果你把打印出来的字符一个接一个排在一起，出现在打印机或屏幕上，你将看到正确的值：4267汉诺塔问题递归算法分析：　　一个庙里有三个柱子，第一个有64个盘子，从上往下盘子越来越大。要求庙里的老和尚把这64个盘子全部移动到第三个柱子上。移动的时候始终只能小盘子压着大盘子。而且每次只能移动一个。　　1、此时老和尚（后面我们叫他第一个和尚）觉得很难，所以他想：要是有一个人能把前63个盘子先移动到第二个柱子上，我再把最后一个盘子直接移动到第三个柱子，再让那个人把刚才的前63个盘子从第二个柱子上移动到第三个柱子上，我的任务就完成了，简单。所以他找了比他年轻的和尚（后面我们叫他第二个和尚），命令：         ①你丫把前63个盘子移动到第二柱子上        ②然后我自己把第64个盘子移动到第三个柱子上后         ③你把前63个盘子移动到第三柱子上     2、第二个和尚接了任务，也觉得很难，所以他也和第一个和尚一样想：要是有一个人能把前62个盘子先移动到第三个柱子上，我再把最后一个盘子直接移动到第二个柱子，再让那个人把刚才的前62个盘子从第三个柱子上移动到第三个柱子上，我的任务就完成了，简单。所以他也找了比他年轻的和尚（后面我们叫他第三和尚），命令：         ①你把前62个盘子移动到第三柱子上         ②然后我自己把第63个盘子移动到第二个柱子上后        ③你把前62个盘子移动到第二柱子上　　3、第三个和尚接了任务，又把移动前61个盘子的任务依葫芦话瓢的交给了第四个和尚，等等递推下去，直到把任务交给了第64个和尚为止（估计第64个和尚很郁闷，没机会也命令下别人，因为到他这里盘子已经只有一个了）。　　4、到此任务下交完成，到各司其职完成的时候了。完成回推了：第64个和尚移动第1个盘子，把它移开，然后第63个和尚移动他给自己分配的第2个盘子。第64个和尚再把第1个盘子移动到第2个盘子上。到这里第64个和尚的任务完成，第63个和尚完成了第62个和尚交给他的任务的第一步。　　从上面可以看出，只有第64个和尚的任务完成了，第63个和尚的任务才能完成，只有第2个和尚----第64个和尚的任务完成后，第1个和尚的任务才能完成。这是一个典型的递归问题。现在我们以有3个盘子来分析：第1个和尚命令：        ①第2个和尚你先把第一柱子前2个盘子移动到第二柱子。（借助第三个柱子）        ②第1个和尚我自己把第一柱子最后的盘子移动到第三柱子。        ③第2个和尚你把前2个盘子从第二柱子移动到第三柱子。　　　很显然，第二步很容易实现（哎，人总是自私地，把简单留给自己，困难的给别人）。其中第一步，第2个和尚他有2个盘子，他就命令：        ①第3个和尚你把第一柱子第1个盘子移动到第三柱子。（借助第二柱子）        ②第2个和尚我自己把第一柱子第2个盘子移动到第二柱子上。         ③第3个和尚你把第1个盘子从第三柱子移动到第二柱子。　　　同样，第二步很容易实现，但第3个和尚他只需要移动1个盘子，所以他也不用在下派任务了。（注意：这就是停止递归的条件，也叫边界值）第三步可以分解为，第2个和尚还是有2个盘子，命令：         ①第3个和尚你把第二柱子上的第1个盘子移动到第一柱子。         ②第2个和尚我把第2个盘子从第二柱子移动到第三柱子。        ③第3个和尚你把第一柱子上的盘子移动到第三柱子。                 分析组合起来就是：1→31→23→2借助第三个柱子移动到第二个柱子|1→3自私人留给自己的活|2→12→31→3借助第一个柱子移动到第三个柱子|共需要七步。如果是4个盘子，则第一个和尚的命令中第1步和第3步各有3个盘子，所以各需要7步，共14步，再加上第1个和尚的1步，所以4个盘子总共需要移动7+1+7=15步，同样，5个盘子需要15+1+15=31步，6个盘子需要31+1+31=64步……由此可以知道，移动n个盘子需要（2的n次方）-1步。　　　从上面整体综合分析可知把n个盘子从1座（相当第一柱子）移到3座（相当第三柱子）：（1）把1座上（n-1）个盘子借助3座移到2座。    （2）把1座上第n个盘子移动3座。（3）把2座上（n-1）个盘子借助1座移动3座。下面用hanoi（n,a,b,c）表示把1座n个盘子借助2座移动到3座。很明显:   (1)步上是hanoi(n-1,1,3,2)             (3)步上是hanoi(n-1,2,1,3)用C语言表示出来，就是：#includeintmethod(intn,chara,charb){    printf("number..%d..form..%c..to..%c.."n",n,a,b);    return0;}inthanoi(intn,chara,charb,charc){    if(n==1)move(1,a,c);    else        {             hanoi(n-1,a,c,b);             move(n,a,c);             hanoi(n-1,b,a,c);        };     return0;}intmain(){    intnum;    scanf("%d",&num);    hanoi(num,'A','B','C');    return0;}