《04递归算法讲解》由会员分享，可在线阅读，更多相关《04递归算法讲解（7页珍藏版）》请在金锄头文库上搜索。
1、1. 用递归法计算 n!【讲解】递归是算法设计中的一种基本而重要的算法。递归方法即通过函数或过程调用自身将问 题转化为本质相同但规模较小的子问题，是分治策略的具体体现。递归方法具有易于描述、证明简单等优点，在动态规划、贪心算法、回溯法等诸多算法 中都有着极为广泛的应用，是许多复杂算法的基础。递归概述一个函数在它的函数体内调用它自身称为递归(recursion)调用。是一个过程或函数 在其定义或说明中直接或间接调用自身的一种方法，通常把一个大型复杂的问题层层转化为 一个与原问题相似的规模较小的问题来求解。递归策略只需少量的程序就可描述出解题过程 所需要的多次重复计算，大大地减少了程序的代码量。递
2、归的能力在于用有限的语句来定义 对象的无限集合。用递归思想写出的程序往往十分简洁易懂。 一般来说，递归需要有边界 条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递 归返回。使用递归要注意以下几点：(1) 递归就是在过程或函数里调用自身；(2) 在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。例如有函数r如下：int r(int a) b=r(a-1);return b;这个函数是一个递归函数，但是运行该函数将无休止地调用其自身，这显然是不正确的。 为了防止递归调用无终止地进行，必须在函数内有终止递归调用的手段。常用的办法是加条 件判断，满足某种条
3、件后就不再作递归调用，然后逐层返回。构造递归方法的关键在于建立递归关系。这里的递归关系可以是递归描述的，也可以是 递推描述的。例 4-1 用递归法计算 n!。n!的计算是一个典型的递归问题。使用递归方法来描述程序，十分简单且易于理解。(1) 描述递归关系递归关系是这样的一种关系。设U,U,U,U,是一个序列，如果从某一项k开始，123 nU 和它之前的若干项之间存在一种只与 n 有关的关系，这便称为递归关系。n注意到，当n三1时，n!=n*(n-l)! (n=0时，0!=1),这就是一种递归关系。对于特定 的k!，它只与k与(k-1)!有关。(2) 确定递归边界在步骤1的递归关系中，对大于k的
4、U的求解将最终归结为对U的求解。这里的U称 nkk为递归边界(或递归出口)。在本例中，递归边界为k=0，即0!=1。对于任意给定的N!,程 序将最终求解到 0! 。确定递归边界十分重要，如果没有确定递归边界，将导致程序无限递归而引起死循环。 例如以下程序：#include int f(int x) return(f(x-1);main() printf(f(5);它没有规定递归边界，运行时将无限循环，会导致错误。(3) 写出递归函数并译为代码将步骤 1 和步骤2 中的递归关系与边界统一起来用数学语言来表示，即n!= n*(n 1)! 当 n1 时n!= 1 当 n=1 时再将这种关系翻译为代码
5、，即一个函数：long f(int n) long g;if(n0) printf(n0, 输入错误！);else if(n=1) g=1;else g=n*f(n 1);return(g);(4) 完善程序主要的递归函数已经完成，设计主程序调用递归函数即可。#include long f(int n) long g;if(nO) printf (n0,输入错误！)；else if(n=1) g=1;else g=n*f(n-1);return(g);void main() int n;long y;prin tf( 计算 n!,请输入 n: );scanf(%d, &n);y=f(n);pr
6、intf( %d!=%ld n,n,y);程序中给出的函数 f 是一个递归函数。主函数调用 f 后即进入函数 f 执行,如果 nO,n=O或n=1时都将结束函数的执行，否则就递归调用f函数自身。由于每次递归调用 的实参为n-1，即把n-l的值赋予形参n，最后当n-l的值为1时再作递归调用，形参n的 值也为 1，将使递归终止，然后可逐层退回。下面我们再举例说明该过程。设执行本程序时输入为 5，即求 5!。在主函数中的调用 语句即为y=f(5)，进入f函数后，由于n=5，不等于0或1,故应执行f=f(n-1)*n,即 f=f(5-1)*5。该语句对f作递归调用即f(4)。进行4次递归调用后，f函数
7、形参取得的值变为1,故不再继续递归调用而开始逐层返 回主调函数。f( 1)的函数返回值为1，f(2)的返回值为1*2=2, f(3)的返回值为2*3=6, f(4) 的返回值为6*4=24，最后返回值f(5)为24*5=120。综上，得出构造一个递归方法基本步骤，即描述递归关系、确定递归边界、写出递归函 数并译为代码，最后将程序完善。2. 汉诺塔(Hanoi),又称河内塔问题，是印度的一个古老传说。开天辟地的神勃拉玛在一 个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余 一个比一个小，依次叠上去。庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中
8、间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上 面。后来,这个传说就演变为汉诺塔游戏:木桩B木桩C木桩C图1图35-1汉诺塔游戏示意图(1) 有三根桩子A、B、C。A桩上有n个碟子，最大的一个在底下，其余一个比一个 小，依次叠上去。(2) 每次移动一块碟子，小的只能叠在大的上面。(3) 把所有碟子从A桩全部移到C桩上，如图35-1所示。试求解n个圆盘A桩全部移到C桩上的移动次数，并求出n个圆盘的移动过程。【讲解】1. 递归关系当 n=1 时，只一个盘，移动一次即完成。当 n=2 时，由于条件是一次只能移动一个盘，且不允许大盘放在小盘上面，首先把小盘 从A桩移到B桩；然后把大盘从A
9、桩移到C桩；最后把小盘从B桩移到C桩，移动3次完成。设移动n个盘的汉诺塔需g(n)次完成。分以下三个步骤：(1) 首先将n个盘上面的n-1个盘子借助C桩从A桩移到B桩上，需g(n-1)次；(2) 然后将A桩上第n个盘子移到C桩上(1次)；(3) 最后，将 B 桩上的 n-1 个盘子借助 A 桩移到 C 桩上，需 g(n-1) 次。因而有递归关系：g(n)=2*g(n-1)+1初始条件(递归出口)：g(1)=1.2. 递归求解汉诺塔移动次数的程序设计/ 汉诺塔 n 盘移动次数#includevoid main()double g(int m);/ 确定初始条件int n;printf( 请输入盘
10、片数 n: );scanf(%d,&n);if(n1 时，分以下三步：(1) 将A桩上面的n-1个盘子借助C桩移到B桩上，即hn(n-l,a,c,b)；(2) 将A桩上第n个盘子移到C桩上，即mv(a,c)；(3) 将B桩上的n-1个盘子借助A桩移到C桩上，即hn(n-l,b,a,c)。在主程序中，用hn(m,l,2,3)带实参m,l,2,3调用hn(n,a,b,c)，这里m为具体移动盘 子的个数。同时设置变量k统计移动的次数。2. 展示汉诺塔移动过程的程序设计函数mv(x,y)输出从x桩到y桩的过程，这里x,y分别不同情况取“A”或“B”或“C”， 主函数调用 hn(m,A,B,C)。/ 展
11、示汉诺塔移动过程的递归设计#include int k=0;void mv(char x,char y)/ 输出函数 printf( %c-%c,x,y);k+;/ 统计移动次数if(k%5=0)printf(n);void hn(int m,char a,char b,char c) / 递归函数 if(m=1) mv(a,c);else hn(m-1,a,c,b);mv(a,c);hn(m-1,b,a,c);#include void main() / 主函数 int n;printf(n input n: ); scanf(%d,&n);hn(n,A,B,C);printf(n k=%d
12、 n,k); / 输出移动次数3. 程序运行示例与分析运行程序， input n： 4A-BA-CB-CA-BC-AC-BA-BA-CB-CB-AC-AB-CA-BA-CB-Ck=15(1) 上面的运行结果是实现函数hn(4,A,B,C)的过程，可分解为以下三步：1) A-B A-C B-C A-B C-A C-B A-B， 这前 7 步是实施 hn(3,A,C,B),即完成把上面3个盘从A桩借助C移到B桩。2) AC这1步是实施着mv(A,C)，即把最下面的盘从A桩移到C桩。3) B-C B-A C-A B-C A-B A-C B-C， 这后 7 步是实施 hn(3,B,A,C),即完成把B
13、桩的3个盘借助A移到C桩。(2) 其中实现hn(3,A,C,B)的过程，可分解为以下三步：1) AB AC BC，这前3步是实施hn(2,A,B,C),即完成把上面两个盘从A桩 借助 B 移到 C 桩。2) AB,这1步是实施mv(A,B),即把第3个盘从A桩移到B桩。3) C-A CB AB,这后3步是实施hn(2,C,A,B),即完成把C桩的两个盘借 助 A 移到 B 桩。从以上的结果分析可进一步帮助对递归的理解。选做3.把前n2个正整数1，2，.，n2从左上角开始，由外层至中心按顺时针方向 螺旋排列所成的数字矩阵，称n阶顺转方阵；按逆时针方向螺旋排列所成的称n阶逆转方 阵。下面即为一个5阶顺转方阵与5阶逆转方阵。12345116151413161718196217242312152425
