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

通常,一个函数在调用另一个函数之前,要作如下的事情: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);这个例子相对简单一些,递归程序如下:intf_recursive(intn){intu1,u2,f;if(n2)f=n+1;else{u1=f_recursive((int)(n/2));u2=f_recursive((int)(n/4));f=u1*u2;}returnf;}下面按照我们上面说的,确定好递归调用树的结构,这一步是最重要的.首先,什么是叶子结点,我们看到当n2时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,下面给出我花了两天功夫想出来的非递归程序(再次提醒你不要气馁,大家都是这么过来的).代码:intf_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)例子二快速排序算法递归算法如下:代码:voidswap(intarray[],intlow,inthigh){inttemp;temp=array[low];array[low]=array[high];array[high]=temp;}intpartition(intarray[],intlow,inthigh){intp;p=array[low];while(lowhigh){while(lowhigh&&array[high]=p)high--;swap(array,low,high);while(lowhigh&&array[low]=p)low++;swap(array,low,high);}returnlow;}voidqsort_recursive(intarray[],intlow,inthigh){intp;if(lowhigh){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)叶子结点:当lowhigh时;e)可以看出这是一个先序调用的二叉树.栈:要保存的数据是两个表示范围的坐标.代码:voidqsort_nonrecursive(intarray[],intlow,inthigh){intm[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++;}}3)例子三阿克曼函数:代码:akm(m,n)=n+1;(m=0时)akm(m-1,1);(n=0时)akm(m-1,akm(m,n-1));(m!=0且n!=0时)递归算法如下:代码:intakm_recursive(intm,intn){inttemp;if(m==0)return(n+1);elseif(n==0)returnakm_recursive(m-1,1);else{temp=akm_recursive(m,n-1);returnakm_recursive(m-1,temp);}}这道题的难点就是确定递归调用树的情况,因为从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)调用,原来在系统机械化的实现递归调用的过程中,这个调用也是一棵子树,不过经过分析,我们用修改栈中数据的方式进行了改进.代码intakm_nonrecursive(intm,intn){intm1[50],n1[50],cp;cp=0;m1[0]=m;n1[0]=n;do{while(m1[cp]0){/*压栈,直到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(cp0||m1[cp]0);returnn1[0]+1;}递归算法详解C通过运行时堆栈支持递归函数的实现。递归函数就是直接或间接调用自身的函数。许多教科书都把计算机阶乘和菲波那契数列用来说明递归，非常不幸我们可爱的著名的老潭老师的《C语言程序设计》一书中就是从阶乘的计算开始的函数递归。导致读过这本经书的同学们，看到阶乘计算第一个想法就是递归。但是在阶乘的计算里，递归并没有提供任