数据结构-递归算法

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

1、递归算法(Recursion)本章内容递归算法定义递归算法举例递归算法复杂性的计算递归算法递归(Recursion)定义直接或间接地调用自身的算法称为递归算法直接或间接调用自身的函数称为递归函数尾递归是指递归调用的语句在递归函数的最后一句递归算法的特点：用于解决一类递归定义的问题算法易于实现，简单明了递归算法递归算法：1(n=0,1)n!=n(n-1)！(n>1)函数的递归调用1.定义：在调用一个函数的过程中直接或间接地调用该函数本身。直接调用intf(x)intx;{inty,z;…..z=f(x);……return(2*z);}f函数调用f函数intf1(x)intx;{inty

2、,z;…..z=f2(y);……return(2*z);}intf2(t)intt;{inta,c;…..c=f1(a);……return(3+c);}间接调用特点是无终止的递归调用，因此，应该给定一个限制递归次数的条件。f1函数调用f2函数f2函数调用f1函数floatfac(intn){floatf;if(n<0)printf(“n<0,dataerror!”);elseif(n==0

3、

4、n==1)f=1;elsef=fac(n-1)*n;returnf;}例如：写一函数求n!以求4的阶乘为例：fac(4)=4*fac(3)fac(3)=3*fac(2)fac(2)=2*fa

5、c(1)fac(1)=1fac(4)=4*3*2*1fac(2)=2*1fac(3)=3*2*1下推回代利用栈实现递归调用主程序(1)输出f(4);……4f(4);（1）n=4top(2)s=4*f(3)n3f(3);（2）n=3（1）n=4top(3)s=3*f(2)n2f(2);（3）n=2（2）n=3（1）n=4top(4)s=2*f(1)n1（4）n=1（3）n=2（2）n=3（1）n=4topss=3*2*1;(2)3(1)4tops=2*1(3)2(2)3(1)4tops=4*3*2*1(1)4top返回(3)2(2)3(1)4top(4)1结束输出24递归的执行情况分析

6、longFact(intn){longs;if(n==1)s=1;elses=n*Fact(n-1);return(s);}使用递归的准则如果待解决的问题具备下列两个特性，就可以考虑使用递归。1)复杂的问题可以转换为简单些的1个或几个子问题；2)最简单的问题可以直接解决例1.3斐波那契(Fibonacci)序列：F0=F1=1Fi=Fi-1+Fi-2（i>1)算法求斐波那契数procedureF(n)//返回第n个斐波那契数//integernifn≤1thenreturn(1)elsereturn(F(n-1)+F(n-2))endifendF算法效率：对F(n-1)、F(n-2)

7、存在大量的重复计算，可以改进算法：保存中间结果例1.4欧几里得算法已知两个非负整数a和b，且a＞b≥0，求这两个数的最大公因数。辗转相除法：若b=0，则a和b的最大公因数等于a；若b＞0，则a和b的最大公因数等于b和用b除a的余数的最大公因数。算法1.8求最大公因数procedureGCD(a,b)//约定a>b//ifb=0thenreturn(a)elsereturn(GCD(b,amodb))endifendGCD例：GCD(22,8)=GCD(8,6)=GCD(6,2)=GCD(2,0)=2;例1.5递归在非数值算法设计中的应用已知元素x，判断x是否在A（1：n）中。算法在A

8、（1：n）中检索xprocedureSEARCH(i)//如果在A（1：n）//中有一元素A（k）=x，则将其第一次出现的下标k返回，否则返回0//globaln,x,A(1:n)case:i>n:return(0):A(i)=x;return(i):else:return(SEARCH(i+1))endcaseendSEARCH子程序的调用形式递归算法的实现机制主程序CallA1:……子程序A一次调用主程序CallA1:……CallA2:……子程序A多次调用…1STACK…1/2STACK主程序CallA1:……子程序ACallB2:…子程序B嵌套调用子程序A主程序CallB1:…

9、…子程序BCallA2:…平行调用递归算法的实现机制…12STACK…12STACK2.递归算法设计定义递归（数学公式，数列等的定义。）数据结构递归（单链表，树，二叉树）可用递归解决的问题P（hanoi问题）问题P具有大规模不同规模的问题P，具有相同性质；并且大规模的问题由小规模的问题构成小规模的问题是可解的关键：找到递归的递推关系找到结束递归的条件3.递归算法设计递归求解的伪代码procedureP(参数表)beginif满足递归出口then简单操作el