(重要)递归(含代码执行过程解释)

递归算法详细分析- C读(17418 )c支持通过运行时栈实现递归函数。 递归函数是直接或间接调用自己的函数。很多教科书都是用来递归地解释计算机阶乘和斐波那契数列的，但是遗憾的是我们可爱的著名老潭老师的C语言程序设计本书是从阶乘计算开始的函数递归。 读了这本经书的学生们看到了阶乘计算的最初想法是递归的。 但是阶乘的计算并没有提供递归的任何优点。 在斐波那契数列中，效率更低是非常可怕的。这里有一个说明递归的简单程序。 程序的目的是将整数从二进制格式转换为可打印的字符格式。 例如，为了给定值42至67，需要顺序地生成字符“4”、“2”、“6”和“7”。 执行与在printf函数中使用%d格式代码时相同的处理。我们采用的策略是将该值除以10，打印各馀数。 例如，除4267的10的馀数是7，但不能直接打印这个馀数。 我们必须印刷的是机器字符集表示数字“7”的值。 在ASCII代码中，字符“7”的值为55，因此为了获得正确的字符，必须加48，但是，使用字符常量而不是整数常量可以提高程序的可移植性。 “0”的ASCII代码为48，所以馀数加上“0”的话，有以下关系零零=0零一=一零二=二是.根据这些关系，若在馀数上加“0”，则容易生成与字符对应的代码。 接下来，打印馀数。 下一步，4267/10将是426。 对这个值重复上述步骤。处理方法的问题只是数字顺序相反，打印方向相反。 因此我们的程序递归地修正这个问题。我们程序的函数具有递归的性质。 因为这包含了对自己的调用。 乍一看，函数似乎永远不会结束。 函数被调用时，它本身就被调用，即使是第二次调用，它本身也被调用，好像永远被调用。 这也是刚接触到递归，最不想知道的事。 但是，实际上这种事情并没有发生。这个程序的递归实现了某种类型的螺旋状while循环。 while循环在每次执行循环整体时都必须取得某种进展，逐渐接近循环结束条件。 递归函数也一样，每次递归调用都必须接近约束。 如果递归函数满足此限制，则递归函数本身不调用。程序中，递归函数的制约条件是变量quotient为零。 因为每次递归调用quotient都除以10，所以每次递归调用，其值都接近零。 最终为零的话递归地结束。接受/*整数值(无符号，转换为字符打印，前导零被删除*/#includeint binary _ to _ ascii (未指示的intvalue )举止无符号内部quotient；quotient=值/10；if(quotient！=0)binary_to_ascii(quotient )putchar (值% 100 )以下递归如何能以正确的顺序打印文字呢？ 此函数的工作流程如下所示。1 .参数值除以102 .如果quotient的值不是零，则调用二进制到ascii打印quotient的当前值的各位数3 .接下来，打印除以步骤1的馀数注意在第二步中，必须打印quotient当前值的各位数字。 我们面临的问题和第一个问题完全相同，只是变量quotient的值变小了。 我们使用刚才创建的函数(将整数转换成单个数字打印)解决了这个问题。 由于quotient的值越来越小，递归最终结束。理解递归后，阅读递归函数最简单的方法是相信递归函数会顺利完成其任务，而不是与其执行过程相关。 如果所有步骤都正确，则只要正确设置了限制，并且每次调用后接近限制，递归函数就总是能正确完成任务。但是，为了理解递归工作原理，需要跟踪递归调用的执行过程，所以我们来继续这项工作吧。 跟踪递归函数执行过程的密钥是了解函数声明的变量是如何存储的。 调用函数时，该变量的空间将在运行时堆栈中创建。 以前调用的函数的变量保留在堆栈中，但隐藏在新函数的变量中，因此无法访问。递归函数调用自己，就会变成这样。 每次进行新调用时，都会创建一组变量，用于屏蔽上次调用递归函数时创建的变量。 在跟踪递归函数的执行过程时，必须区分分数不同的调用变量，以避免混淆。程序中的函数有两个变量：参数value和局部变量quotient。 下图显示了堆栈的状态，当前可以访问的变量位于堆栈的顶部。 所有其他调用变量都用灰色阴影装饰，表示无法访问当前正在执行的函数。假设用值4267调用递归函数。 函数开始执行时，堆栈的内容如下图所示执行除法运算后，堆栈的内容如下然后，if语句确定quotient的值不为零，因此对该函数执行递归调用。 第二次调用此函数时，堆栈的内容如下在堆栈上创建新变量，隐藏上一个变量。 他们无法访问，除非通过这次递归调用返回。 再次执行除法运算后，堆栈的内容如下因为quotient的值现在是42，还不是零，所以必须继续递归调用并创建一组变量。 执行这次呼叫的出发运算后，堆栈的内容如下此时，quotient的值不是0，需要执行递归调用。 执行除法运算后，堆栈的内容如下不是递归地调用语句本身，而是迄今为止执行的语句只是测试除法和quotient的值。 由于递归地调用这些语句并反复执行，所以它的效果类似于循环，其中quotient的值不为零时，该循环将该值作为初始值来恢复循环。 但是，递归调用存储的信息与存储在堆栈中的变量值不同。 这些信息很快就变得重要。如果quotient的值为零，递归函数将开始打印输出，而不调用自己。 函数返回，开始丢弃堆栈上的变量值。每次调用putchar时，都会获得变量value的最后一个数字，将value除以类型10，得到0到9之间的整数。 将其加到字符常数0上，结果输出与该数字相对应的ASCII字符。输出4 :函数返回变量已从堆栈中丢弃。 然后，递归函数的上次调用重新开始，她正在使用自己的变量，他们位于堆栈的顶部。 因为值为42，所以调用putchar输出的数字为2。输出42 :其次，递归函数的这次调用也被返回，该变量也被丢弃，堆栈最上面的是递归函数再次被调用的变量。 递归调用从该位置继续执行，这次打印的数字是6。 在这次调用返回之前，堆栈的内容如下输出426 :现在展开整个递归过程，返回到函数的第一个调用。 这次调用打印数值7，即value参数除以10的馀数。输出4267 :然后该递归函数完全返回到调用其他函数的位置。在打印机或画面上依次排列打印的文字，显示正确的值： 4267汉诺塔问题递归算法分析：一个庙有三个柱子，一个有64个盘子，从上到下都是大盘子。 我想让寺里的老僧把这64个盘子移到第三根柱子上。 移动的时候总是只有小盘子捂着大盘子。 一次只能移动一个。1、这时老和尚(后来我们叫第一个和尚)觉得很难，所以有人觉得前63个盘子可以先移到第二根柱子上，就把最后一个盘子直接移到第三根柱子上，让那个人把刚才的前63个盘子从第二根柱子移到第三根柱子上于是他命令寻找比他年轻的僧侣(后来我们叫他第二个僧侣) :你把前63个盘子移到第二柱然后，我自己把第64个盘子移动到第三个柱子上后请把前63个盘子移动到第三柱上二、第二个和尚接受任务也很难，他也和第一个和尚一样想。 如果有人能把前62个盘子首先移动到第三根柱子上，把最后一个盘子直接移动到第二根柱子上，让那个人把刚才的前62个盘子从第三根柱子移动到第三根柱子上，我的任务就完成了，很简单。 于是他又找了比他年轻的僧侣(我们叫他第三个僧侣)，命令道：请把前62个盘子移到第三柱然后我自己把第63个盘子移动到第二个柱子上后请把前62个盘子移到第二柱上三三个僧侣接手了任务，还把移动前的61盘任务用葫芦语、葫芦语、葫芦语、葫芦语、葫芦语交给了第四个僧侣，直到任务交给第64个僧侣为止。4、在这项任务下完成，到了各部门完成其职务的时候了。 结束了：第64个和尚移动第一个盘子，放开它，第63个和尚移动分配给自己的第二个盘子。第六十四个僧侣把第一个盘子移到第二个盘子里。 这里完成了第64个僧侣的任务，第63个僧侣完成了第62个僧侣交给他的任务的第一步。从上面可以看出，第64个僧侣的任务完成了，第63个僧侣的任务完成了，第2个僧侣第64个僧侣的任务完成了，第1个僧侣的任务完成了。 这是典型的递归问题。 用三个盘子分析一下吧。第一个僧侣的命令：第二个僧侣请把第一根柱子前面的两个盘子移到第二根柱子上。 (通过第三根柱子)第一个和尚，我自己把第一根柱子的最后一个盘子移到第三根柱子上。第二个僧侣把前两个盘子从第二根柱子移到第三根柱子上。显然，第二步很容易实现(啊，人总是自私，把简单留给自己，把困难给别人)。第一步是，第二个僧侣有两个盘子，他命令道第三个僧侣把第一根柱子的第一个盘子移到第三根柱子上。 (通过第二柱)第二个和尚，我自己把第一根柱子的第二个盘子移到第二根柱子上。第三个僧侣把第一个盘子从第三根柱子移到第二根柱子上。同样，第二步很容易实现，但第三僧侣只需移动一个盘子，所以不需要交给部下任务。 (注意：这是停止递归的条件，也称为边界值。)第三步可以命令，分解为第二僧侣还有两个盘子第三个僧侣把第二根柱子上的第一个盘子移到第一根柱子上。第二个僧侣，我把第二个盘子从第二根柱子移到第三根柱子上。第三个和尚，请把第一个柱子的盘子移到第三个柱子上。分析的组合需要13 12 32经由第三柱移动到第二柱|13自私的人留下自己的工作| 21 23 13经由第一柱移动到第三柱|合计7个步骤。如果盘子是四个，在第一个僧侣的命令下，因为步骤1和步骤3分别有三个盘子，所以分别需要七步，合计14步，并且因为第一个僧侣需要一步，所以四个盘子合计71，7=15步，同样，五个盘子是15，15=31步从以上的整体综合分析可知，n个盘子从1台(相当于第一柱)移到3台(相当于第三柱)(1)一个(n-1 )个盘子通过三个转移到两个。(2)把第1座的第n个盘子移动3座。(3)2个(n-1 )个盘子用1个移动3个。以下，在hanoi(n、a、b、c )中，显示了通过两台将一台n个盘子移动到三台。说明了： (1)步是hanoi(n-1、1、3、2 )(3)步骤为Hanoi (n-1，2，1，3 )用c语言来表达的话#includeint method(int n，char a，char b )举止printf ( num