递归和归纳法课件.ppt

(1)递归递归是一种十分重要的程序设计方法,对于一些问题,用递归方法设计算法可使算法简洁明了,逻辑清晰,易于设计。递归指算法自己调用自己,相应的算法称为递归算法。递归分类:直接递归与间接递归递归方法:解决一类满足递归关系的问题。递归本质:对原问题的求解可转化为对其性质相同的子问题的求解。基于归纳的递归算法(递归概念)基于归纳的递归算法(递归概念)例子:计算阶乘函数算法计算阶乘函数输入:输出:过程:1 ifn=0thenreturn12elsereturnn*fatorial(n-1)递归关系(特性):产生递归的基础。递归出口(结束条件):确定递归的层数。参数设置:参数表示了原问题及其不同的子问题。基于归纳的递归算法(归纳的思想方法)(2)归纳法的思想方法对于一个规模为n的问题p(n),归纳法的思想方法是:基础步:a1是问题p(1)的解。归纳步:对所有的k,1kn,若b是问题p(k)的解,则p(b)是问题p(k+1)的解。其中,p(b)是对问题的某种运算或处理。例如。因为a1是问题p(1)的解,若a2=p(a1),a2是问题p(2)的解;以此类推,an-1是问题p(n-1)的解,且an=p(an-1),则an是问题p(n)的解。 因此,求解问题p(n)的解an,可先求问题p(n-1)的解an-1,然后再对an-1进行p运算或处理。为求问题p(n-1)的解,先求问题p(n-2)的解,如此不断进行递归求解。直至p(1)为止。当得到p(1)的解之后,再返回来,不断地把所得的解进行p运算或处理,直至p(n)的解为止。这就是基于归纳的递归算法的思想方法。基于归纳的递归算法(选择排序),可以如下进行:基础步:当n=1时,数组A[2n]的最小者A[j],A[j]与A[1]交换,A[1]有排序。归纳步:如果A[1n-1]的n-1个元素已经排序,则A[n]有序。:n个元素的数组A[1n]输出:按非降序排列数组A[1n]1. sort(1)过程sort(i)1 ifi<nthen2 k=i基于归纳的递归算法(选择排序)3forj=i+1ton4ifA[j]<A[k]then5k=j6endfor7ifkithen互换A[i]和A[k]8sort(i+1)9endif最坏情况下时间复杂性算法分析:由基础步知:当n=1时,A[1]要有序,元素比较次数为n-1;当A[1n-1]已经排序,即前n-1个元素有序时,A[n]自然有序。可由归纳步知,总比较次数C(n)为:基于归纳的递归算法(插入排序),可以如下进行:基础步:当n=1时,数组只有一个元素,它已排序。归纳步:如果前面k-1个元素已经排序,只要对第k个元素逐一与前面的k-1个元素比较,把它插入适当位置,即可完成k个元素的排序。算法InsertionSort输入:n个元素的数组A[1n]输出:按非降序排列数组A[1n]1. sort(n)过程:sort(i)1 ifi>1then2 x=A[i]3 sort(i-1)基于归纳的递归算法(插入排序)3 j=i-14whilej>0andA[j]>x5 A[j+1]A[j]6j=j+17endwhile8 A[j+1]=x9endif最坏情况下时间复杂性算法分析:由基础步知:当n=1时,即只有一个元素已经有序,元素比较次数为0;当n>1时,可由归纳步知,总比较次数C(n)为:基于归纳的递归算法(整数幂),其高效算法描述如下:算法Exprec输入:实数x和非负整数n输出:1. power(x,n)过程:power(x,m)基于归纳的递归算法(整数幂)ifm=0theny=1else y=power(x,m/2) y=y2 ifm为奇数theny=xyendif7 returny最坏情况下时间复杂性算法分析:乘法次数C(n)为:: Pn(x)=anxn+an-1xn-1+…+a1x+a0 则根据Horner规则,得 Pn(x)=(…((an)x+an-1)x+an-2)x+an-3)x…)x+a1)x+a0 Pn(x)=xPn-1(x)+a0 由归纳知:基于归纳的递归算法(n阶多项式)基础步:当n=0时,有P0(x)=an。归纳步:对于任意的k,1kn,如果前面k-1步已计算出pk-1: Pk-1(x)=anxk-1+an-1xk-2+…+an-k+2x+an-k+1则有: Pk(x)=xPk-1(x)+an-k