2022年递归算法详解 .pdf

《2022年递归算法详解 .pdf》由会员分享，可在线阅读，更多相关《2022年递归算法详解 .pdf（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、递归算法详解C 通过运行时堆栈支持递归函数的实现。递归函数就是直接或间接调用自身的函数。许多教科书都把计算机阶乘和菲波那契数列用来说明递归，非常不幸我们可爱的著名的老潭老师的C 语言程序设计一书中就是从阶乘的计算开始的函数递归。导致读过这本经书的同学们，看到阶乘计算第一个想法就是递归。但是在阶乘的计算里，递归并没有提供任何优越之处。在菲波那契数列中，它的效率更是低的非常恐怖。这里有一个简单的程序， 可用于说明递归。 程序的目的是把一个整数从二进制形式转换为可打印的字符形式。例如：给出一个值4267，我们需要依次产生字符4，2，6，和 7。就如在 printf 函数中使用了 %d 格式码，它就会

2、执行类似处理。我们采用的策略是把这个值反复除以10，并打印各个余数。例如，4267 除 10的余数是 7，但是我们不能直接打印这个余数。我们需要打印的是机器字符集中表示数字 7的值。在 ASCII 码中，字符 7的值是 55，所以我们需要在余数上加上48来获得正确的字符， 但是，使用字符常量而不是整型常量可以提高程序的可移植性。0的 ASCII 码是 48，所以我们用余数加上0，所以有下面的关系：0+ 0 = 00+ 1 = 10+ 2 = 2 . 从这些关系中，我们很容易看出在余数上加上0就可以产生对应字符的代码。接着就打印出余数。下一步再取商的值，4267/10 等于 426。然后用这个值

3、重复上述步骤。这种处理方法存在的唯一问题是它产生的数字次序正好相反，它们是逆向打印的。所以在我们的程序中使用递归来修正这个问题。我们这个程序中的函数是递归性质的,因为它包含了一个对自身的调用。乍一看，函数似乎永远不会终止。当函数调用时，它将调用自身，第2 次调用还将调用自身，以此类推，似乎永远调用下去。这也是我们在刚接触递归时最想不明白的事情。但是，事实上并不会出现这种情况。这个程序的递归实现了某种类型的螺旋状while 循环。while 循环在循环体每次执行时必须取得某种进展，逐步迫近循环终止条件。递归函数也是如此，它在每次递归调用后必须越来越接近某种限制条件。当递归函数符合这个限制条件时，

4、它便不在调用自身。在程序中，递归函数的限制条件就是变量quotient 为零。在每次递归调用之前，我们都把 quotient 除以 10，所以每递归调用一次，它的值就越来越接近零。当它最终变成零时，递归便告终止。/*接受一个整型值（无符号0，把它转换为字符并打印它，前导零被删除*/ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 9 页 - - - - - - - - - #include int binary_to_ascii( unsigned int value)

5、unsigned int quotient; 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 当前值的各位数字。我们所面临的问题和最初的

6、问题完全相同，只是变量quotient 的值变小了。我们用刚刚编写的函数（把整数转换为各个数字字符并打印出来）来解决这个问题。 由于 quotient的值越来越小，所以递归最终会终止。一旦你理解了递归，阅读递归函数最容易的方法不是纠缠于它的执行过程，而是相信递归函数会顺利完成它的任务。如果你的每个步骤正确无误，你的限制条件设置正确，并且每次调用之后更接近限制条件，递归函数总是能正确的完成任务。但是，为了理解递归的工作原理，你需要追踪递归调用的执行过程，所以让我们来进行这项工作。追踪一个递归函数的执行过程的关键是理解函数中所声明的变量是如何存储的。当函数被调用时，它的变量的空间是创建于运行时堆栈

7、上的。以前调用的函数的变量扔保留在堆栈上，但他们被新函数的变量所掩盖，因此是不能被访问的。当递归函数调用自身时，情况于是如此。每进行一次新的调用，都将创建一批变量，他们将掩盖递归函数前一次调用所创建的变量。当我追踪一个递归函数的执行过程时，必须把分数不同次调用的变量区分开来，以避免混淆。程序中的函数有两个变量：参数value 和局部变量 quotient 。下面的一些图显示了堆栈的状态，当前可以访问的变量位于栈顶。所有其他调用的变量饰以灰色的阴影，表示他们不能被当前正在执行的函数访问。假定我们以 4267 这个值调用递归函数。当函数刚开始执行时，堆栈的内容如下图所示：名师资料总结 - - -精

8、品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 9 页 - - - - - - - - - 执行除法之后，堆栈的内容如下：接着， if 语句判断出 quotient 的值非零，所以对该函数执行递归调用。当这个函数第二次被调用之初，堆栈的内容如下：堆栈上创建了一批新的变量，隐藏了前面的那批变量，除非当前这次递归调用返回，否则他们是不能被访问的。再次执行除法运算之后，堆栈的内容如下：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精

9、心整理 - - - - - - - 第 3 页，共 9 页 - - - - - - - - - quotient 的值现在为 42，仍然非零，所以需要继续执行递归调用，并再创建一批变量。在执行完这次调用的出发运算之后，堆栈的内容如下：此时， quotient 的值还是非零，仍然需要执行递归调用。在执行除法运算之后，堆栈的内容如下：不算递归调用语句本身，到目前为止所执行的语句只是除法运算以及对quotient 的值进行测试。由于递归调用这些语句重复执行，所以它的效果类似循环：当 quotient 的值非零时，把它的值作为初始值重新开始循环。但是，递归调用将会保存一些信息（这点与循环不同），也就好

10、是保存在堆栈中的变量值。这些信息很快就会变得非常重要。现在 quotient 的值变成了零，递归函数便不再调用自身，而是开始打印输出。然后函数返回，并开始销毁堆栈上的变量值。每次调用 putchar 得到变量 value 的最后一个数字，方法是对value 进行模 10 取余运算，其结果是一个0 到 9 之间的整数。把它与字符常量0相加，其结果便是对应于这个数字的ASCII 字符，然后把这个字符打印出来。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 9 页 - - -

11、- - - - - - 输出 4：接着函数返回，它的变量从堆栈中销毁。接着，递归函数的前一次调用重新继续执行，她所使用的是自己的变量， 他们现在位于堆栈的顶部。因为它的 value 值是 42，所以调用 putchar 后打印出来的数字是2。输出 42：接着递归函数的这次调用也返回，它的变量也被销毁，此时位于堆栈顶部的是递归函数再前一次调用的变量。递归调用从这个位置继续执行，这次打印的数字是6。在这次调用返回之前，堆栈的内容如下：输出 426：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - -

12、- 第 5 页，共 9 页 - - - - - - - - - 现在我们已经展开了整个递归过程，并回到该函数最初的调用。这次调用打印出数字 7，也就是它的 value 参数除 10 的余数。输出 4267 ：然后，这个递归函数就彻底返回到其他函数调用它的地点。如果你把打印出来的字符一个接一个排在一起，出现在打印机或屏幕上，你将看到正确的值： 4267汉诺塔问题递归算法分析：一个庙里有三个柱子， 第一个有 64 个盘子，从上往下盘子越来越大。要求庙里的老和尚把这64 个盘子全部移动到第三个柱子上。 移动的时候始终只能小盘子压着大盘子。而且每次只能移动一个。1、此时老和尚（后面我们叫他第一个和尚）

13、觉得很难，所以他想：要是有一个人能把前 63 个盘子先移动到第二个柱子上， 我再把最后一个盘子直接移动到第三个柱子，再让那个人把刚才的前63 个盘子从第二个柱子上移动到第三个柱子上，我的任务就完成了，简单。所以他找了比他年轻的和尚（后面我们叫他第二个和尚），命令： 你丫把前 63 个盘子移动到第二柱子上 然后我自己把第64 个盘子移动到第三个柱子上后 你把前 63 个盘子移动到第三柱子上2、第二个和尚接了任务，也觉得很难，所以他也和第一个和尚一样想：要是有一个人能把前62 个盘子先移动到第三个柱子上， 我再把最后一个盘子直接移动到第二个柱子，再让那个人把刚才的前62 个盘子从第三个柱子上移动到

14、第三个柱子上，我的任务就完成了， 简单。所以他也找了比他年轻的和尚 （后面我们叫他第三和尚） ，命令： 你把前 62 个盘子移动到第三柱子上 然后我自己把第63 个盘子移动到第二个柱子上后名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 9 页 - - - - - - - - - 你把前 62 个盘子移动到第二柱子上3、第三个和尚接了任务，又把移动前61 个盘子的任务依葫芦话瓢的交给了第四个和尚，等等递推下去，直到把任务交给了第64 个和尚为止（估计第64 个和尚很郁闷，没

15、机会也命令下别人，因为到他这里盘子已经只有一个了）。4、到此任务下交完成，到各司其职完成的时候了。完成回推了：第 64 个和尚移动第 1 个盘子，把它移开，然后第63 个和尚移动他给自己分配的第2 个盘子。第 64 个和尚再把第1 个盘子移动到第2 个盘子上。到这里第 64 个和尚的任务完成，第 63 个和尚完成了第62 个和尚交给他的任务的第一步。从上面可以看出，只有第64 个和尚的任务完成了，第63 个和尚的任务才能完成，只有第 2 个和尚 -第 64 个和尚的任务完成后，第1 个和尚的任务才能完成。这是一个典型的递归问题。现在我们以有3 个盘子来分析：第 1 个和尚命令： 第 2 个和尚

16、你先把第一柱子前2 个盘子移动到第二柱子。（借助第三个柱子） 第 1 个和尚我自己把第一柱子最后的盘子移动到第三柱子。 第 2 个和尚你把前 2 个盘子从第二柱子移动到第三柱子。很显然，第二步很容易实现（哎，人总是自私地，把简单留给自己，困难的给别人）。其中第一步，第2 个和尚他有 2 个盘子，他就命令： 第 3 个和尚你把第一柱子第1 个盘子移动到第三柱子。 （借助第二柱子） 第 2 个和尚我自己把第一柱子第2 个盘子移动到第二柱子上。 第 3 个和尚你把第 1 个盘子从第三柱子移动到第二柱子。同样，第二步很容易实现，但第3 个和尚他只需要移动1 个盘子，所以他也不用在下派任务了。（注意：这

17、就是停止递归的条件，也叫边界值）第三步可以分解为，第2 个和尚还是有2 个盘子，命令： 第 3 个和尚你把第二柱子上的第1 个盘子移动到第一柱子。 第 2 个和尚我把第 2 个盘子从第二柱子移动到第三柱子。 第 3 个和尚你把第一柱子上的盘子移动到第三柱子。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 9 页 - - - - - - - - - 分析组合起来就是：13 12 32 借助第三个柱子移动到第二个柱子|13 自私人留给自己的活 | 21 23 13 借助第一个

18、柱子移动到第三个柱子|共需要七步。如果是 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 座上（

19、 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 语言表示出来，就是：#include int method(int n,char a, char b) printf(number.%d.form.%c.to.%c.n,n,a,b); return 0; int hanoi(int n,char a,char b,char c) if( n=1 ) move (1,a,c); else hanoi(n

20、-1,a,c,b); move(n,a,c); hanoi(n-1,b,a,c); ; return 0; int main() i nt num; scanf(%d,&num); hanoi(num,A,B,C); return 0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 9 页 - - - - - - - - - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 9 页 - - - - - - - - -