页数：41页文件大小：969.0 KB来源： 计算机语言与程序设计ppt课件
本课件围绕递归算法展开，先讲或结点、与结点、多关联点与结点等概念，画出求n!的与或结点图并说明调用与返回的递归过程，再比较递归与递推的差异，随后以哈诺塔与青蛙过河两道经典例题演示如何把问题分解为可直接求解的结点，给出递归公式与完整C语言参考程序。
本页为第六讲 递归章节封面，本讲系统讲解递归概念、与或结点图、哈诺塔与青蛙过河等递归问题。
递归算法在可计算性理论中占有重要地位，它是算法设计的有力工具，对于拓展编程思路非常有用。就递归算法而言并不涉及高深数学知识，只不过初学者要建立起递归概念不十分容易。先从最简单的例子导入——用递归算法求 n!
定义：函数 fact(n) = n! fact(n-1) = (n-1)! 则有 fact(n) = n * fact(n-1) 已知 fact(1) = 1为了表述得直观清晰，定义两个结点：或结点与与结点。A 为“或结点”，A 依不同条件会有两种不同的取值 B 或 C。
如果有多于 2 种取值，可用下图表示：条件为 Z1, Z2, …, Zn，取值为 B 或 C, … 或 G。
仍以求 n! 为例画出与或图：A 为或结点；B 为直接可解结点，值为 1；C 为与结点，当 n>1 时 A 的取值即 C 的值，而 C 的值即 E 的值；为了求得 E 的值，需要先求出 D 的值，D 值 fact(n-1) 乘以 n 即为 E 的值。
与结点可能有多个相关联的点，这时可描述为下图：A 结点的值最终为 D 的值，但为了求 D 需先求 B 和 C。从图上看先求左边的点才能求最右边的点的值，我们约定最右边 D 点的值就是 A 结点的值。
下面我们以 3！为例来画与或结点图，目的是体会递归的含义：
C = 1 D = 2*C = 2 B = D = 2 E = 3*B = 3*2 = 6 A = E = 6本页画出了调用和返回的递归示意图，展示 fact 函数层层调用自身、到达边界后再逐层返回的过程。
从图可以想象：欲求 fact(3)，先要求 fact(2)；要求 fact(2) 先求 fact(1)。就象剥一颗圆白菜，从外向里一层层剥下来，到了菜心遇到 1 的阶乘其值为 1，到达了递归的边界。然后再用 fact(n)=n*fact(n-1) 这个普遍公式，从里向外倒推回去得到 fact(n) 的值。为了把这个问题说得再透彻一点，另画了如下流程图。
本页以流程图形式展示求阶乘时的递归调用与返回流程，源文件未给出更多文字说明。
为了形象地描述递归过程，将上图改画成下图。
在这个图中“内层”与“外层”有着相同的结构，它们之间“你中有我，我中有你”，呈现相互依存的关系。为讲清递归概念，将递归与递推做一比较，仍以求阶乘为例。递推是从已知的初始条件出发，逐次去求所需要的阶乘值：
初始条件 fact(1) = 1 fact(2) = 2*fact(1) = 2 fact(3) = 3*fact(2) = 6递推相当于从菜心“推到”外层。而递归算法的出发点不放在初始条件上，而放在求解的目标上，从所求的未知项出发逐次调用本身的求解过程，直到递归的边界（即初始条件）。
就本例而言读者会认为递归算法可能多余、费力不讨好，但许多实际问题不可能或不容易找到显而易见的递推关系，这时递归算法就表现出明显优越性：符合人的思维方式，逻辑性强，可读性好、易于理解。下面举一个尽人皆知的例子——哈诺（Hanoi）塔问题。
故事：相传在古代印度的 Bramah 庙中，有位僧人整天把三根柱子上的金盘倒来倒去，原来他是想把 64 个一个比一个小的金盘从一根柱子移到另一根柱子上去。移动过程恪守规则：每次只允许移动一只盘，且大盘不得落在小盘上面。
有人会觉得这很简单，真的动手移盘就会发现：如以每秒移动一只盘子计算，将 64 只盘子移完所需时间约为 5800 亿年。
怎样编写这种程序？从思路上还是先从最简单的情况分析起，搬一搬看，慢慢理出思路。
move 1 from A to Cmove 1 from A to B; move 2 from A to C; move 3 from B to C;move(2, A, C, B)move 3 from A to Cmove(2, B, A, C)所谓借助是什么意思，等这件事做完了不言自明。
本页以图示方式展示 A 柱上有 3 只盘子时的整体转移过程，源文件未给出更多文字说明。
move(2, A, C, B) 实际上分解为以下三步：第(1).1步：move 1 from A to C; 第(1).2步：move 2 from A to B; 第(1).3步：move 1 from C to B;同样，3 号盘一旦到了 C，move(2, B, A, C) 也要分解为三步：
第(3).1步：move 1 from B to A; 第(3).2步：move 2 from B to C; 第(3).3步：move 1 from A to C;move(2, A, C, B) 是说要将 2 只盘子从 A 搬至 B，但没有 C 是不行的，因为第(1).1步就要将 1 盘从 A 移到 C，给 2 盘创造条件，然后再把 1 盘从 C 移至 B，由此明白借助 C 的含义。因此在构思搬移过程的参量时，要把 3 个柱子都用上move(n, A, B, C)，物理意义是将 n 只盘子从 A 经 B 搬到 C考虑到前面研究过的 (1)(2)(3) 步，可把搬移过程用与或结点图表示。
这里用与或结点的含义是分解为 (1)(2)(3) 步，这 3 步是相关的、相互依存的，而且是有序的，从左至右执行：
move(n-1, A, C, B)：将上面的 n-1 只盘子作为一个整体从 A 经 C 移至 Bn：A to C：将 n 号盘从 A 移至 C，是直接可解结点move(n-1, B, A, C)：将上面的 n-1 只盘子作为一个整体从 B 经 A 移至 C这里显然是一种递归定义。当解 move(n-1, A, C, B) 时又可想到将其分解为 3 步：
move(n-2, A, B, C)n-1: A to Bmove(n-2, C, A, B)下面仍以 3 只盘子为例画出递归的与或图。
这个图很象一颗倒置着的树：结点 move(3, A, B, C) 是树根，与结点是树的分枝，叶子都是直接可解结点。
本页以图形方式给出哈诺塔递归分解树，源文件未给出更多文字说明。
本页继续以图形方式展示哈诺塔递归结构与盘号移动顺序，源文件未给出更多文字说明。
#include <stdio.h> int step=1;void move(int , char ,char,char);void main() { int n; printf("请输入盘数n=" ); scanf("%d",&n); printf("在3根柱子上移%d只盘的步骤为:\n",n); move(n,'a','b','c'); } void move(int m, char p, char q, char r) { if (m==1) { printf("[%d] move 1# from %c to %c\n", step, p, r); step=step+1; } else { move(m-1,p,r,q); printf("[%d] move %d# from %c to %c\n", step, m, p, r); step=step+1; move(m-1,q,p,r); } }本页以图示方式收束哈诺塔问题的递归实现，源文件未给出更多文字说明。
讨论问题——青蛙过河。该题是 2000 年全国青少年信息学奥林匹克的一道试题，叙述如下：
一条小溪尺寸不大，青蛙可以从左岸跳到右岸。左岸有一石柱 L，面积只容一只青蛙落脚，右岸也有一石柱 R，同样只容一只。有一队青蛙从小到大用 1，2，…，n 编号，初始时只能趴在左岸的石头 L 上，按号一个落一个，小的落在大的上面，不允许大的在小的上面。
小溪中有 S 个石柱、y 片荷叶：溪中柱子上允许一只青蛙落脚，如有多只同样要求按号大的在下小的在上；荷叶只允许一只青蛙落脚，不允许多只在其上；右岸石柱 R 与左岸石柱 L 一样允许多个青蛙按号叠落。
青蛙从左岸 L 跳走后不允许再跳回来；从左岸 L 跳至右岸 R，或从溪中荷叶、溪中石柱跳至右岸 R 上的青蛙也不允许再离开。问：已知溪中有 S 根石柱和 y 片荷叶，最多能跳过多少只青蛙？
这题看起来较难，但认真分析、理出思路就可化难为易。
Jump(S,y)——最多可跳过河的青蛙数，其中 S 为河中柱子数、y 为荷叶数S=0，Jump(0,y)。当 y=1 时 Jump(0,1)=2：河中有一片荷叶可以过两只青蛙，起始时 L 上有两只青蛙，1# 在 2# 上面当 y=2 时 Jump(0,2)=3：河中有两片荷叶时可以过 3 只青蛙。起始时 1#、2#、3# 落在 L 上：
采用归纳法：Jump(0,y)=y+1，意思是河中没有石柱时，过河的青蛙数仅取决于荷叶数，数目是荷叶数+1。
再看 Jump(S, y)。先看一个最简单情况：S=1，y=1，从图上看出需要 9 步，跳过 4 只青蛙：
| 时刻 | L1 | L2 | L3 | L4 | S1 | S2 | Y | R1 | R2 | R3 | R4 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| t=0 | 1 | 2 | 3 | 4 | — | — | — | — | — | — | — |
| t=1 | 2 | 3 | 4 | — | — | — | 1 | — | — | — | — |
| t=2 | 3 | 4 | — | — | — | 2 | 1 | — | — | — | — |
| t=3 | 3 | 4 | — | — | 1 | 2 | — | — | — | — | — |
| t=4 | 4 | — | — | — | 1 | 2 | 3 | — | — | — | — |
| t=5 | — | — | — | — | 1 | 2 | 3 | 4 | — | — | — |
| t=6 | — | — | — | — | 1 | 2 | — | 3 | 4 | — | — |
| t=7 | — | — | — | — | 2 | — | 1 | 3 | 4 | — | — |
| t=8 | — | — | — | — | — | — | 1 | 2 | 3 | 4 | — |
| t=9 | — | — | — | — | — | — | — | 1 | 2 | 3 | 4 |
说明：源文件该页内容以图示与粘连字符形式给出（L1~L4、S1~S2、Y、R1~R4 各位置按时刻 0~9 排列），上表按前后页所述的九步跳法还原，供对照原图核对。
为把过河过程描述得更清楚，给出了表 1。表中 L1 L2 L3 L4 表示左岸石柱上落在一起的青蛙的高度位置，L1 在最上面、L4 在最下面；同理 R1 R2 R3 R4 也是如此。对水中石柱 S 分成两个高度位置 S1、S2；对荷叶 Y 无须分层，因为它只允许一只青蛙落在其上。
这一过程是一分为二的过程：将 L 上的一队青蛙分解为两个队，每队各二只，并把上面的二只转移到 S 上。于是可形成两个系统：L、Y、R 系统与 S、Y、R 系统，前者二只青蛙号大，后者二只青蛙号小，先跳号大的、再跳号小的。从第五步到第九步可以看出的确是这么做的。
对于 LYR 系统，相当于 Jump(0,1)；对于 SYR 系统，相当于 Jump(0,1)。两个系统之和为 2*Jump(0,1)，因此：
Jump(1,1) = 2*Jump(0,1) = 2*2 = 4现在再看 S=2、y=1 的 Jump(2,1)：将河中两个石柱称作 S1 和 S2，荷叶叫 y，考虑先将 L 上青蛙的一半借助于 S2 和 y 转移到 S1 上，一半小号的青蛙在 S1 上、大的留在 L 上。
这样 L S1 S2 y R 系统分解为：
（L S2 y R系统）+（S1 S2 y R系统） = 2 *（L S2 y R系统） = 2 * Jump(1,1)用归纳法得：Jump(S, y) = 2*Jump(S-1, y)
5. 将上述分析出来的规律写成递归形式的与或结点图。
举例：S=3，y=4，算 Jump(3,4)。由 Jump(0,y)=y+1 与 Jump(S,y)=2*Jump(S-1,y) 可得 Jump(3,4)=2*Jump(2,4)=4*Jump(1,4)=8*Jump(0,4)=8*5=40，即最多可跳过 40 只青蛙。
说明：源文件该页仅给出“举例：S=3，y=4，算 Jump(3,4)”的标题性内容，上式为依据前两页递推关系补算的示例结果，供对照原图核对。
#include <stdio.h> int Jump(int, int);void main() { int s,y,sum; printf("请输入石柱数s=" ); scanf("%d",&s); printf("请输入荷叶数y=" ); scanf("%d",&y); sum=Jump(s,y); printf("Jump(%d,%d)=%d\n",s,y,sum); } int Jump(int r,int z) { int k; if (r==0) { k=z+1; } else { k=2*Jump(r-1,z); } return(k); }本页为第六讲 递归的结束页，本讲内容至此结束。
下载地址：{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}