第6章递归算法

《第6章递归算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章递归算法递归不是一种数据结构，还是一种有效的算法设计方法。递归算法是指算法直接或间接地调用其本身。许多应用问题的算法，用递归来定义或描述，概念更清晰。比如：⑴n!的定义：6.1递归的概念1当n=0或1时n(n-1)…1当n>1时n!=6-11当n=0或1时n(n-1)!当n>1时n!=6-2或定义为：⑵问题的解决存在自调用在有序数组a中查找数据元素k是否存在的折半查找算法。查找思想用Low、High和Mid表示待查找区间的下界、上界和中间位置指针，初值为Low=1，High=n。1当n=0或1时nf(n-1)当n>1时f(n)=6-3若定义为函数形

2、式则为：⑴取中间位置Mid：Mid=(Low+High)/2；⑵比较中间位置记录的关键字与给定的K值：①相等：查找成功；②大于：待查记录在区间的前半段，修改上界指针：High=Mid-1，转⑴；③小于：待查记录在区间的后半段，修改下界指针：Low=Mid+1，转⑴；直到越界(Low>High)，查找失败。算法示例如图6-1(a)，(b)所示。查找215131921375664758088921234567891011MidHighLow5131921375664758088921234567891011MidHighLow5131921375664758088

3、921234567891011MidHighLow(a)查找成功示例查找71-5131723384656657881921234567891011MidHighLow-5131723384656657881921234567891011MidHighLow-5131723384656657881921234567891011MidHighLow-5131723384656657881921234567891011MidHighLow(b)查找不成功示例图6-1折半查找示例在用计算机实现递归算法时，必须是有限的。为了防止递归调用无终止地进行，必须有终止递归调用的条件

4、，一旦满足该条件后就不再进行递归，然后逐层返回。例：计算n!。6.2递归算法的执行过程1!=1(终止条件)要求n!，先求(n-1)!要求(n-1)!，先求(n-2)!要求3!，先求2!要求2!，先求1!┇递推n!=n(n-1)!3!=32!┇回推求得n!2!=21!/*递归调用计算阶乘*/longfact(intn){longf;if(n>1)f=fact(n-1)*n;elsef=1;return(f);}main(){intn;longy;scanf("%d",&n);y=fact(n);printf("%d!=%ld",n,y);getchar()

5、;}Fact(n)=1当n=1时终止条件n*fact(n-1)当n>0时递推规则intBin_Search(inta[],intkey,intlow,inthigh){intMid;if(Low>High)return(-1);//查找失败Mid=(low+high)/2;if(key==a[Mid])return(Mid);//查找成功elseif(key

6、cludemain(void){inta[]={1,3,4,5,9,17,18,25,31,33,57};intx=17;intpos;pos=BSearch(a,x,0,11);if(bn==-1)printf("x不在数组a中");elseprintf("x在数组a的下标%d中",pos);}基本思想：将一个较为复杂的问题，分解成若干个相对简单且类同的子问题，这样就可递推得到解。能用递归算法求解的问题的充分必要条件是：⑴问题具有某种可借用的类同自身的子问题描述的性质；⑵某一有限步的子问题（也称作本原问题）有直接的解存在。当一个问题具有上述两个

7、基本要素时，该问题就可以用递归算法解决。6.3递归算法的设计方法递归算法的设计方法⑴把对原问题的求解设计成包含有对子问题求解的形式。⑵设计递归出口。设计举例：设计模拟汉诺塔问题求解过程的算法。问题描述：设有3根标号为A，B，C的柱子，在A柱上放着n个盘子，每一个都比下面的略小一点，要求把A柱上的盘子全部移到C柱上。移动规则：①一次只能移动一个盘子；②移动过程中大盘子不能放在小盘子上面；③移动过程中盘子可以放在任意一个柱子上。问题分析：可以用递归方法求解n个盘子的汉诺塔问题。基本思想：1个盘子的汉诺塔问题可直接移动。n个盘子的汉诺塔问题可递归表示为：首先把上边的n-

8、1个盘子从