递归算法

必考+加试·信息技术第四单元递归算法必考+加试·信息技术考点与典例考点递归算法1.递归的概念函数或过程调用其本身,称为递归。2.递归算法的基本思想递归算法的基本思想是把规模较大的、较难解决的问题变成规模较小的、容易解决的同一问题,规模较小的问题又变成规模更小的问题,直到可以直接得出它的解,从而得到原来问题的解。3.采用递归算法需具备的条件(1)每一步骤解决问题的方法要一致。(2)要有结束的边界条件。必考+加试·信息技术【典例1】小明利用下面的方法求2i(2的i次方)的值:如果i=0,则2i=1,否则将2i转换为2*2i-1,而2i-1又可以转换为2*i-2,如此继续,从而求出了2i的值。小明采用的算法是()A.解析算法B.枚举算法C.递归算法D.查找算法解析:本题考查的是递归算法的基本思想。本题中求2i的值,采用“大事化小,小事化了”的方法,符合递归算法的基本思想。答案:C必考+加试·信息技术【典例2】下列VB程序中,f是一个递归函数。Functionf(nAsInteger)AsLongIfn=0Thenf=1Elsef=f(n-1)+5EndIfEndFunctionPrivateSubCommand1_Click()DimyAsLong必考+加试·信息技术y=f(5)Label1.Caption=Str(y)EndSub程序运行时,单击命令按钮Command1后,在标签Label1中显示的内容是()A.1B.5C.21D.26必考+加试·信息技术解析:本题考查的是递归算法的程序实现。这段程序有两部分组成:事件处理过程(PrivateSubCommand1_Click())和自定义函数(Functionf(nAsInteger)AsLong)。在自定义函数f中又出现了调用函数f本身的语句f=f(n-1)+5,因此f函数采用的是递归算法。在事件处理过程PrivateSubCommand1_Click()中,语句y=f(5)表示调用函数f,将参数5传递给f函数中的变量n,最终将函数的返回值赋给变量y。y=f(5)=5+5+5+5+5+1=26,因此在标签Label1中显示的内容为26。答案:D必考+加试·信息技术【典例3】下列程序的功能是求两个整数m,n的最大公约数。其算法思想为:输入两个数,如果两个数相等,则最大公约数是其本身(m或n);如果不相等,取两个数中的较小数和这两个数差的绝对值进行比较,若相等则为最大公约数,不等则继续使用上述方法求解,直到相等为止。Functiongcd(m,n)AsIntegerIfm=nThengcd=mElsegcd=gcd()EndIfEndFunctionPrivateSubCommand1_Click()必考+加试·信息技术DimmAsInteger,nAsInteger,tAsIntegerm=Val(Text1.Text)n=Val(Text2.Text)IfmnThent=m:m=n:n=tLabel1.Caption=Str(gcd(m,n))EndSub为实现上述功能,程序划线处应填入的语句为()A.m,nB.n,m-nC.m,Abs(m-n)D.n,Abs(m-n)必考+加试·信息技术解析:本题主要考查递归算法的程序实现。根据算法可知,若当前两个数不相等,则取较小数n和这两个数差的绝对值(Abs(m-n))再进行比较,因此答案为D。答案:D必考+加试·信息技术点击进入课时训练