递归算法详解

递归算法详解标准化管理处编码[BBX968T-XBB8968-NNJ668-MM9N]

冯文科一、递归的基本概念。一个函数、概念或数学结构，如果在其定义或说明内部直接或间接地出现对其本身的引用，或者是为了描述问题的某一状态，必须要用至它的上一状态，而描述上一状态，又必须用到它的上一状态……这种用自己来定义自己的方法，称之为递归或递归定义。在程序设计中，函数直接或间接调用自己，就被称为递归调用。二、递归的最简单应用：通过各项关系及初值求数列的某一项。在数学中，有这样一种数列，很难求出它的通项公式，但数列中各项间关系却很简单，于是人们想出另一种办法来描述这种数列：通过初值及％与前面临近几项之间的关系。要使用这样的描述方式，至少要提供两个信息：一是最前面几项的数值，一是数列间各项的关系。比如阶乘数列1、2、6、24、120、720……如果用上面的方式来描述它，应该是：如果需要写一个函数来求匕的值，那么可以很容易地写成这样：intf(intn)if(n==1)return1;returnn*f(n-1);这就是递归函数的最简单形式，从中可以明显看出递归函数都有的一个特点：先处理一些特殊情况一一这也是递归函数的第一个出口，再处理递归关系一一这形成递归函数的第二个出口。递归函数的执行过程总是先通过递归关系不断地缩小问题的规模，直到简单到可以作为特殊情况处理而得出直接的结果，再通过递归关系逐层返回到原来的数据规模，最终得出问题的解。以上面求阶乘数列的函数f(n)为例。如在求f(3)时，由于3不是特殊值，因此需要计算3*f(2)，但f⑵是对它自己的调用，于是再计算f(2)，2也不是特殊值，需要计算2*f(1)，需要知道f(1)的值，再计算f(1)，1是特殊值，于是直接得出f(1)=1，返回上一步，得f(2)=2*f(1)=2，再返回上一步，得f(3)=3*f(2)=3*2=6，从而得最终解。用图解来说明，就是

【例1】数列｛"J的前几项为1A 11+1 . 1 11+干1+—T-1+—1+1输入n，编程求an的精确分数解。分析:这个题目较易，发现a=1,其它情况下有a= 。如要求实数解的话，这基n1+an-1本已经可以写出递归函数了。但由于题目要求精确的分数解，还需做一些调整。设即得an。但发现a=q，则由递归关系，有a即得an。但发现n-1p n1+a qp+qn-1 1+—一个问题：求出〃时，需要返回两个整数：分子q与分母p，而通常的函数只能返回一n-1个整数。这个问题一般有两类解决办法，一种是让求值函数返回一个结构体变量，这样就可以返回两个变量了(其实还可以不只两个呢)；另一种是在求值函数的参数表中加入两个指针变量或引用变量，通过参数给带回数值。但由于后一种做法会使程序结构不清晰一一返回值是由参数表得到的，因此我们使用前一种方法。另外，在通过a=q得出a=—L后，a就已经是最简分数了，无须化简。证n-1pnp+qn明如下：若q是最简分数，即说明p,q的最大公约数为1，即对任何1<r<q，都有qmodr与Ppmodr不全为0，不防记qmodr=a、pmodr=b，则有只要a与b不全为0，且a<r,b<r，就有a与(a+b)modr不全为0。因此对任何的1<r<q，有pmodr与(p+q)modr不全为0。而对于q<r<p的情况而言，记pmodr=a，则有由于0<a<r,0<q<r，因此同样有pmodr与(p+q)modr不全为0。所以对任意1<r<p，都有pmodr与(p+q)modr不全为0，因此它们的最大公约数为1，即_L是最简分数。虽然这是个要求a(即q)是最简分数的结论，但由于数p+q n-1 p列第二项为2，是最简分数，因此可以证明第三项也是最简分数，同时也证明对所有的a，求出的工就是最简分数，无须化简。n p+q具体代码如下：N(0<N<9)0—Nii+1i+2NNNiNi2i+12(i+1),MAX*sizeof(char));t[n]='\0';for(i=0;i<n;i++)(t[q[i]]='Q';cout<<t<<endl;t[q[i]]='.';)cout<<endl;booltest(inti,intk)(intj;j=0；while(j<k&&abs(j-k)!=abs(q[j]-i))j++；if(j==k&&mark[i]==false)returntrue;elsereturnfalse;)voidsearch(intk)(if(k==n)write();c++;return;)inti;for(i=0;i<n;i++)if(test(i,k))(mark[i]=true;q[k]=i;search(k+1);mark[i]=false;))intmain()

六、练习【练习】为给定的表达式建立表达式树，并求值。给定的表达式中，所有数字都是1位正整数，出现的符号可能为+、一、*、/、（、）。分析：这是一个与一般数据结构书上讲的用栈计算的方法本质不同的方法。在详细说明这个算法之前，需要首先明确这个算法用到的概念1、单元：一个单元可能是用括号括起来的一个表达式，或是一个整数；2、项：一个项是指由*与/连接起来的若干单元；3、表达式：一个表达式是指由十或一连接起来的若干项。要建立表达式树，需要三个函数互相调用的函数：一个是getunit,用于建立一个单元；一个是getexpr,用于建立一个项，另一个就是build,用于建立一个表达式。getunit函数较易，如果字符串首字母是（的话，那么从它后面的字符开始用build建立一个表达式，这个表达式就是一个单元；否则，就处理一个整数；getexpr函数是建立在getunit之上的，它先用getunit建立一个单元，然后不停地考察之后地连接符号是不是*或/，若是，则不停地重复读连接符、建立另一个单元、建立连接的操作，直到连接符号不是*或/为止。build函数是用于最终建立表达式的，它先用getexpr建立一个项，再用符号将剩余的各项连接成二叉树。代码如下：if(n>0){ hanoi(n-1,x,z,y); hanoi(n-1,y,x,z); }.w[10]中intknap(ints,intn)(算法32是求n个数的和的递归算法。算法33是相应的迭代版本。假设n个数已存储在数组a的分量a[1]，…,a[n]中。floatsum(intn){.a[n]都置为0a[0]=1; *//* */voidmain()(inti;for(i=0;i<5;i++)printf("%d!=%d\n”,i,factorial(i));/*递归阶乘函数调用*//*========================================*/TOC\o"1-5"\h\z/*使用列印数组函数来说明递归调用 *//*========================================*/*/intlist[6]={1,2,3,4,5,6);/*数组内容*//* *//*递归数组反向列印函数 *//* */voidinvert_array(intj)(if(j<6)/*终止条件 *//*递归链表列印函数调用*/invert_array(j+1);printf("[%d]”,list[j]);/*列印元素资料*/))TOC\o"1-5"\h\z/* *//*主程式：反向列印数组内容. *//* */voidmain()(inti;printf（〃数组的内容：\n"）;for(i=0;i<6;i++)printf(z/[%d]/z,list[i]); /*列印元素资料*/printf(/z\n/z); /*换行*/printf(〃递归列印数组的内容:\n〃);invert_array(0); /*调用列印函数*/printf(/z\n/z); /*换行*/递归阶乘函数来说明递归内部处理 */递归阶乘函数intfactrial(intj)intsum=0;/*阶乘总和变数*/inttemp=0;/*阶乘总和暂存变数*/ifintsum=0;/*阶乘总和变数*/inttemp=0;/*阶乘总和暂存变数*/if(j==0)/*终止条件 */sum=1;printf(〃到达终止条件(j=0)\n");else%d\n”,printf(〃从函数factrial(%d)调用前的状态：sum%d\n”,j,sum);temp=factrial(j-1); /*递归阶乘函数调用*/printf(〃返回函数factrial(%d)后的状态：sum=%d\n”,j,sum);sum=j*temp;/*计算j!的值*/printf("==＞在计算％d!阶乘后的状态：sum=%d\n”,j,sum);)returnsum;)/* *//*主程式：计算整数4的阶乘.*//* */voidmain()printf("4!=%d\n”,factrial(4));/*递归阶乘函数调用*/*/*/*/*/*/*//*========================================TOC\o"1-5"\h\z/*递归的链表建立和列印 *//*========================================#include<>structlist /*链表结构宣告 */(intdata; /*节点资料 */structlist*next;/*指向下一节点）；/*定义新型态 /*定义新型态 */typedefnode*link; /*定义新型态指标*/TOC\o"1-5"\h\z/* *//*递归链表列印函数 *//* */voidprint_list(linkptr)(if(ptr!=NULL) /*终止条件*/(printf("[%d]”,ptr->data);/*列印节点资料*//*递归链表列印函数调用*/print_list(ptr->next);)

/**//*递归链表建立函数*//**/linkcreate_list(int*array,intlen,intpos)linkhead;/*链表节点的指标/**//*递归链表建立函数*//**/linkcreate_list(int*array,intlen,intpos)linkhead;/*链表节点的指标*/if(pos==len)/*终止条件 */returnNULL;else/*建立节点记忆体*/head=(link)malloc(sizeof(node));if(!head)returnNULL;head->data=array[pos];/*建立节点内容*/head->next=create_list(array,len,pos+1);returnhead;))TOC\o"1-5"\h\z/* *//*主程式：建立链表后将内容印出. *//* */voidmain()(intlist[6]={1,2,3,4,5,6);/*数组内容*/linkhead; /*指向链表开始*/*/head=create_list(list,6,0);/*建立链表

*/if(!head)printf(〃记忆体配置失败!\n〃);exit(1);}printf(〃链表的内容:\n〃);print_list(head); /*列印链表 */printf(〃\n〃)； /*换行 */卜巡/*递归的链表建立和反向列印 */#include<>structlist/*链表结构宣告 structlist/*链表结构宣告 */intdata;/*节点资料intdata;/*节点资料*/TOC\o"1-5"\h\zstructlist*next;/*指向下一节点 */)；typedefstructlistnode;/*定义新型态 */typedefnode*link; /*定义新型态指标*//* *//*递归链表反向列印函数 *//* */voidprint_list(linkptr)(if(ptr!=NULL) /*终止条件 */(/*递归链表列印函数调用*/print_list(ptr->next);TOC\o"1-5"\h\zprintf("[%d]”,ptr->data);/*列印节点资料 */))/* *//*递归链表建立函数 *//* */linkcreate_list(int*array,intlen,intpos)(linkhead; /*链表节点的指标*/if(pos==len) /*终止条件 */returnNULL;else/*建立节点记忆体*/head=(link)malloc(sizeof(node));if(!head)returnNULL;head->data=array[pos];/*建立节点内容*/head->next=create_list(array,len,pos+1);returnhead;TOC\o"1-5"\h\z/* *//*主程式：建立链表后将内容印出. *//* */voidmain()(1,2,3,4,5,6};/*数组内容*/linkhead; /*指向链表开始 */*/head=create_list(list,6,0);/*建立链表*/if(!head)(printf(〃记忆体配置失败！\n〃)；exit(1);)printf(〃链表的内容:\n〃)；print_list(head);/*列印链表*/printf(〃\n〃)； /*换行 */2/*========================================*//*河诺塔问题 *//**//*/**//*TOC\o"1-5"\h\z/*河内塔问题的递归函数 *//* */inthanoi(intdishs,intpeg1,intpeg2,intpeg3)(if(dishs==1) /*终止条件 */printf(〃盘子从%d移到％d\n”,peg1,peg3);else(hanoi(dishs-1,peg1,peg3,peg2);/*第一步骤*/printf(〃盘子从%d移到％d\n”,peg1,peg3);hanoi(dishs-1,peg2,peg1,peg3);/*第三步骤*/

/*主程式：找出河内塔问题的解.voidmain()hanoi(3,1,2,3);hanoi(3,1,2,3);/*调用递归函数*//*应用递归来走迷宫/*数字0:表示是可走的路/*应用递归来走迷宫/*数字0:表示是可走的路/*数字1：表示是墙壁，不可走的路/*数字2:标示是走过的路/*数字2:标示是走过的路*//*========================================*/intmaze[7][10]={ /*迷宫的数组*/TOC\o"1-5"\h\z1, 1, 1, 1, 1, 1, 1, 1, 1, 1,1, 0, 1, 0, 1, 0, 0, 0, 0, 1,1, 0, 1, 0, 1, 0, 1, 1, 0, 1,1, 0, 1, 0, 1, 1, 1, 0, 0, 1,1, 0, 1, 0, 0, 0, 0, 0, 1, 1,1, 0, 0, 0, 1, 1, 1, 0, 0, 1,1, 1, 1, 1, 1, 1, 1, 1, 1, 1);/* *//*走迷宫的递归函数 *//* */intfind_path(intx,inty)if(x==1&&y==1)(maze[x][y]=2;return1;)elseif(maze[x][y]==0)(maze[x][y]=2;if((find_path(x-/*是否是迷宫出口 *//*记录最后走过的路 *//*是不是可以走 *//*记录己经走过的路 */1,y)+/*调用递归函数往上*/find_path(x+1,y)+/*往下 */find_path(x,y-1)+/*往左 */find_path(x,y+1))>0)/*往右*/return1;elsemaze[x][y]=0; /*此路不通取消记号 */return0;elsereturn0;/**//*主程式：用递归的方法在数组迷宫找出口.*//**//*voidmain()

inti,j;TOC\o"1-5"\h\zfind_path(5,8); /*调用递归函数 */printf(〃迷宫的路径如下图所示:\n〃)；for(i=1;i<6;i++) /*印出迷宫的图形 */(for(j=1;j<9;j++)printf(〃％d〃,maze[i][j]);/*印出各座标*/printf(〃\n〃)； /*换行 */)遇/*========================================*//*应用递归来解N皇后问题 *//*数字1：表示是放置皇后 *//*数字0:表示没有放置*//*数字0:表示没有放置*//**//*#defineMAXQUEEN8 /*最大放置的皇后数*/*/intpad[MAXQUEEN][MAXQUEEN]={/*NXN的棋盘*/TOC\o"1-5"\h\z0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0);/* *//*放/*放N个皇后的递归函数*//**//*intput_queen(intx,inty,inttimes)(inti,j,result=0;if(times>MAXQUEEN) /*终止条件*/return1;elseif(place(x,y)) /*检查是否可放置皇后*/(pad[x][y]=1; /*放置皇后*/for(i=0;i<MAXQUEEN;i++)for(j=0;j<MAXQUEEN;j++)(/*递归调用放置下一个皇后*/result+=put_queen(i,j,times+1);if(result>0)break;)if(result>0) /*找到了解*/return1;else(pad[x][y]=0; /*清除皇后*/return0;))elsereturn0;/* *//*检查皇后是否有相互攻击 *//* -*/(End)冯文科一、递归的基本概念。一个函数、概念或数学结构，如果在其定义或说明内部直接或间接地出现对其本身的引用，或者是为了描述问题的某一状态，必须要用至它的上一状态，而描述上一状态，又必须用到它的上一状态……这种用自己来定义自己的方法，称之为递归或递归定义。在程序设计中，函数直接或间接调用自己，就被称为递归调用。二、递归的最简单应用：通过各项关系及初值求数列的某一项。在数学中，有这样一种数列，很难求出它的通项公式，但数列中各项间关系却很简单，于是人们想出另一种办法来描述这种数列：通过初值及匕与前面临近几项之间的关系。要使用这样的描述方式，至少要提供两个信息：一是最前面几项的数值，一是数列间各项的关系。比如阶乘数列1、2、6、24、120、720……如果用上面的方式来描述它，应该是：如果需要写一个函数来求匕的值，那么可以很容易地写成这样：intf(intn)if(n==1)return1;returnn*f(n-1);这就是递归函数的最简单形式，从中可以明显看出递归函数都有的一个特点：先处理一些特殊情况一一这也是递归函数的第一个出口，再处理递归关系一一这形成递归函数的第二个出口。递归函数的执行过程总是先通过递归关系不断地缩小问题的规模，直到简单到可以作为特殊情况处理而得出直接的结果，再通过递归关系逐层返回到原来的数据规模，最终得出问题的解。以上面求阶乘数列的函数f(n)为例。如在求f(3)时，由于3不是特殊值，因此需要计算3*f(2)，但f⑵是对它自己的调用，于是再计算f(2)，2也不是特殊值，需要计算2*f(1)，需要知道f(1)的值，再计算f(1)，1是特殊值，于是直接得出f(1)=1，返回上一步，得f(2)=2*f(1)=2，再返回上一步，得f(3)=3*f(2)=3*2=6，从而得最终解。用图解来说明，就是

【例1】数列｛"J的前几项为1A 11+1 . 1 11+干1+—T-1+—1+1输入n，编程求an的精确分数解。分析:这个题目较易，发现a=1,其它情况下有a= 。如要求实数解的话，这基n1+an-1本已经可以写出递归函数了。但由于题目要求精确的分数解，还需做一些调整。设即得an。但发现a=q，则由递归关系，有a即得an。但发现n-1p n1+a qp+qn-1 1+—一个问题：求出〃时，需要返回两个整数：分子q与分母p，而通常的函数只能返回一n-1个整数。这个问题一般有两类解决办法，一种是让求值函数返回一个结构体变量，这样就可以返回两个变量了(其实还可以不只两个呢)；另一种是在求值函数的参数表中加入两个指针变量或引用变量，通过参数给带回数值。但由于后一种做法会使程序结构不清晰一一返回值是由参数表得到的，因此我们使用前一种方法。另外，在通过a=q得出a=—L后，a就已经是最简分数了，无须化简。证n-1pnp+qn明如下：若q是最简分数，即说明p,q的最大公约数为1，即对任何1<r<q，都有qmodr与Ppmodr不全为0，不防记qmodr=a、pmodr=b，则有只要a与b不全为0，且a<r,b<r，就有a与(a+b)modr不全为0。因此对任何的1<r<q，有pmodr与(p+q)modr不全为0。而对于q<r<p的情况而言，记pmodr=a，则有由于0<a<r,0<q<r，因此同样有pmodr与(p+q)modr不全为0。所以对任意1<r<p，都有pmodr与(p+q)modr不全为0，因此它们的最大公约数为1，即_L是最简分数。虽然这是个要求a(即q)是最简分数的结论，但由于数p+q n-1 p列第二项为2，是最简分数，因此可以证明第三项也是最简分数，同时也证明对所有的a，求出的工就是最简分数，无须化简。n p+q具体代码如下：N(0<N<9)0—Nii+1i+2NNNiNi2i+12(i+1),MAX*sizeof(char));t[n]='\0';for(i=0;i<n;i++)(t[q[i]]='Q';cout<<t<<endl;t[q[i]]='.';)cout<<endl;booltest(inti,intk)(intj;j=0；while(j<k&&abs(j-k)!=abs(q[j]-i))j++；if(j==k&&mark[i]==false)returntrue;elsereturnfalse;)voidsearch(intk)(if(k==n)write();c++;return;)inti;for(i=0;i<n;i++)if(test(i,k))(mark[i]=true;q[k]=i;search(k+1);mark[i]=false;))intmain()

六、练习【练习】为给定的表达式建立表达式树，并求值。给定的表达式中，所有数字都是1位正整数，出现的符号可能为+、一、*、/、（、）。分析：这是一个与一般数据结构书上讲的用栈计算的方法本质不同的方法。在详细说明这个算法之前，需要首先明确这个算法用到的概念1、单元：一个单元可能是用括号括起来的一个表达式，或是一个整数；2、项：一个项是指由*与/连接起来的若干单元；3、表达式：一个表达式是指由十或一连接起来的若干项。要建立表达式树，需要三个函数互相调用的函数：一个是getunit,用于建立一个单元；一个是getexpr,用于建立一个项，另一个就是build,用于建立一个表达式。getunit函数较易，如果字符串首字母是（的话，那么从它后面的字符开始用build建立一个表达式，这个表达式就是一个单元；否则，就处理一个整数；getexpr函数是建立在getunit之上的，它先用getunit建立一个单元，然后不停地考察之后地连接符号是不是*或/，若是，则不停地重复读连接符、建立另一个单元、建立连接的操作，直到连接符号不是*或/为止。build函数是用于最终建立表达式的，它先用getexpr建立一个项，再用符号将剩余的各项连接成二叉树。代码如下：.从这些关系中，我们很容易看出在余数上加上‘0’就可以产生对应字符的代码。接着就打印出余数。下一步再取商的值，4267/10等于426。然后用这个值重复上述步骤。这种处理方法存在的唯一问题是它产生的数字次序正好相反，它们是逆向打印的。所以在我们的程序中使用递归来修正这个问题。我们这个程序中的函数是递归性质的，因为它包含了一个对自身的调用。乍一看，函数似乎永远不会终止。当函数调用时，它将调用自身，第2次调用还将调用自身，以此类推，似乎永远调用下去。这也是我们在刚接触递归时最想不明白的事情。但是，事实上并不会出现这种情况。这个程序的递归实现了某种类型的螺旋状while循环。while循环在循环体每次执行时必须取得某种进展，逐步迫近循环终止条件。递归函数也是如此，它在每次递归调用后必须越来越接近某种限制条件。当递归函数符合这个限制条件时，它便不在调用自身。在程序中，递归函数的限制条件就是变量quotient为零。在每次递归调用之前，我们都把quotient除以10，所以每递归调用一次，它的值就越来越接近零。当它最终变成零时，递归便告终止。/*接受一个整型值(无符号0,把它转换为字符并打印它，前导零被删除*/#include<>intbinary_to_ascii(unsignedintvalue)…d.“一quotient=value/10;if(quotient!=0)binary_to_ascii(quotient);「…1ue递归是如何帮助我们以正确的顺序打印这些字符呢下面是这个函数的工作流程.将参数值除以10.如果quotient的值为非零，调用binary-to-ascii打印quotient当前值的各位数字.接着，打印步骤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个盘子先移动到第三个柱子上，我再把最后一