递归算法教程文件

第四单元(dānyuán)递归算法第一页，共10页。考点(kǎodiǎn)与典例考点(kǎodiǎn)递归算法(suànfǎ)1.递归的概念函数或过程调用其本身,称为递归。2.递归算法的基本思想递归算法的基本思想是把规模较大的、较难解决的问题变成规模较小的、容易解决的同一问题,规模较小的问题又变成规模更小的问题,直到可以直接得出它的解,从而得到原来问题的解。3.采用递归算法需具备的条件(1)每一步骤解决问题的方法要一致。(2)要有结束的边界条件。第二页，共10页。【典例1】小明利用下面的方法求2i(2的i次方)的值:如果i=0,则2i=1,否则将2i转换为2*2i-1,而2i-1又可以转换为2*i-2,如此继续(jìxù),从而求出了2i的值。小明采用的算法是()A.解析算法 B.枚举算法 C.递归算法 D.查找算法解析:本题考查的是递归算法的基本思想。本题中求2i的值,采用(cǎiyòng)“大事化小,小事化了”的方法,符合递归算法的基本思想。答案:C第三页，共10页。【典例2】下列VB程序(chéngxù)中,f是一个递归函数。Functionf(nAsInteger)AsLongIfn=0Thenf=1Elsef=f(n-1)+5EndIfEndFunctionPrivateSubCommand1_Click()DimyAsLong第四页，共10页。y=f(5)Label1.Caption=Str(y)EndSub程序运行时,单击命令按钮Command1后,在标签Label1中显示(xiǎnshì)的内容是()A.1 B.5 C.21 D.26第五页，共10页。解析:本题考查的是递归算法的程序实现。这段程序有两部分组成:事件处理过程(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中显示的内容(nèiróng)为26。答案:D第六页，共10页。【典例3】下列程序的功能是求两个整数m,n的最大公约数。其算法思想为:输入两个数,如果两个数相等(xiāngděng),则最大公约数是其本身(m或n);如果不相等(xiāngděng),取两个数中的较小数和这两个数差的绝对值进行比较,若相等(xiāngděng)则为最大公约数,不等则继续使用上述方法求解,直到相等(xiāngděng)为止。Functiongcd(m,n)AsIntegerIfm=nThengcd=mElsegcd=gcd()EndIfEndFunctionPrivateSubCommand1_Click()第七页，共10页。DimmAsInteger,nAsInteger,tAsIntegerm=Val(Text1.Text)n=Val(Text2.Text)Ifm<nThent=m:m=n:n=tLabel1.Caption=Str(gcd(m,n))EndSub为实现上述(shàngshù)功能,程序划线处应填入的语句为()A.m,n B.n,m-nC.m,Abs(m-n) D.n,Abs(m-n)第八页，共10页。解析:本题主要考查递归算法的程序实现。根据算法可知,若当前两个(liǎnɡɡè)数不相等,则取较小数n和这两个(