算法设计与分析—递归算法.ppt

一、在日常生活中，递归一词较常用于描述以自相似方法重复事物的过程。
例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。
.
2
德罗斯特效应（英语：Droste effect）是递归执行过程。
　　设计：算法的参数包括：有序数组a，要查找的数据元素x，数组下界下标low，数组上界下标high。当在数组a中查找到数据元素x时函数返回数组a的下标；当在数组a中查找不到数据元素x时函数返回-1。
.
12
递归算法如下：
int BSearch(int a[], int x, int low, int high)
{
int mid;
if(low > high) return -1; 　　　//查找不成功 
mid = (low + high) / 2;
if(x == a[mid]) return mid; //查找成功
else if(x < a[mid])
return BSearch(a, x, low, mid-1);//在下半区查找
else
return BSearch(a, x, mid+1, high);//在上半区查找
}
.
13
测试代码设计如下：
# include <> 
main(void)
{ int a[] = {1, 3, 4, 5, 17, 18, 31, 33};
int x = 17;
int bn; 
bn = BSearch(a, x, 0,7);
if(bn == -1) printf("x不在数组a中");
else printf("x在数组a的下标%d中", bn);
}
.
14
BSearch(a, x, 0,7)的递归调用过程如下图所示，其中，实箭头表示过程调用，虚箭头表示过程的返回值。
BSearch(a, x, 0, 7)
…
mid=3
…
return BSearch(a, x, 4, 7)
main()
…
x=17
…
bn = BSearch(a, x, 0, 7)
BSearch(a, x, 4, 7)
…
mid=5
…
return BSearch(a, x, 4, 4)
BSearch(a, x, 4, 4)
…
mid=4
…
return 4
4
4
4
.
15

递归算法既是一种有效的算法设计方法，也是一种有效的分析问题的方法。递归算法求解问题的基本思想是：对于一个较为复杂的问题，把原问题分解成若干个相对简单且类同的子问题，这样较为复杂的原问题就变成了相对简单的子问题；而简单到一定程度的子问题可以直接求解；这样，原问题就可递推得到解。
.
16
并不是每个问题都适宜于用递归算法求解。适宜于用递归算法求解的问题的充分必要条件是：
（1）问题具有某种可借用的类同自身的子问题描述的性质；
（2）某一有限步的子问题（也称作本原问题）有直接的解存在。
.
17
当一个问题存在上述两个基本要素时，设计该问题的递归算法的方法是：
（1）把对原问题的求解设计成包含有对子问题求解的形式。
（2）设计递归出口。
.
18
例6-3 设计模拟汉诺塔问题求解过程的算法。汉诺塔问题的描述是：设有3根标号为A，B，C的柱子，在A柱上放着n个盘子，每一个都比下面的略小一点，要求把A柱上的盘子全部移到C柱上，移动的规则是：（1）一次只能移动一个盘子；（2）移动过程中大盘子不能放在小盘子上面；（3）在移动过程中盘子可以放在A，B，C的任意一个柱子上。　　
问题分析：可以用递归方法求解n个盘子的汉诺塔问题。
.
19
基本思想：
1个盘子的汉诺塔问题可直接移动。n个盘子的汉诺塔问题可递归表示为，首先把上边的n-1个盘子从A柱移到B柱，然后把最下边的一个盘子从A柱移到C柱，最后把移到B柱的n-1个盘子再移到C柱。
4个盘子汉诺塔问题的递归求解示意图如下图所示。
.
20
n-1
n
原柱 A 辅助柱 B 目标柱 C
.
21
算法设计：首先，盘子的个数n是必须的一个输入参数，对n个盘子,我们可从上至下依次编号为1,2,…,n；其次，输入参数还需有3个柱子的代号,我们令3个柱子的参数名分别为fromPeg，auxPeg和toPeg；最后，汉诺塔问题的求解是一个处