函数递归调用堆栈分析.doc

函数递归调用堆栈分析这里有一个庞杂的次序，可用于说明递归。次序的目的是把一个整数从二进制方法转换为可打印的字符方法。比如：给出一个值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，把它转换为字符并打印它，前导零被删除*/#include<stdio.h>intbinary_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个跟尚你把第一柱子上的盘子移动到第三柱子。                  分析组合起来的确是：131232借助第三个柱子移动到第二个柱子|13无公众留给自己的活|212313借助第一个柱子移动到第三个柱子|共需要七步。假定是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座。上面用hanoin,a,b,c表示把1座n个盘子借助2座移动到3座。特不清晰:   (1)步上是hanoi(n-1,1,3,2)             (3)步上是hanoi(n-1,2,1,3)用C语言表示出来，的确是：#include<stdio.h>intmethod(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;