1、(1)递归递归递归是一种十分重要的程序设计方法,对于一些问题,用递归方法设计算法可使算法简洁明了,逻辑清晰,易于设计。n递归递归指算法自己调用自己,相应的算法称为递归算法递归算法。n递归分类:递归分类:直接递归与间接递归n递归方法:递归方法:解决一类满足递归关系的问题。n递归本质:递归本质:对原问题的求解可转化为对其性质相同的子问题的求解。基于归纳的递归算法基于归纳的递归算法(递归概念递归概念)基于归纳的递归算法基于归纳的递归算法(递归概念递归概念)例子:计算阶乘函数)!1(nn!n!n0n0n1算法算法 计算阶乘函数 输入:输入:输出:输出:过程:过程:1if n=0 then return
2、 12 else return n*fatorial(n-1)!nnn递归关系递归关系(特性特性):产生递归的基础。n递归出口递归出口(结束条件结束条件):确定递归的层数。n参数设置:参数设置:参数表示了原问题及其不同的子问题。)(nfactorial!n基于归纳的递归算法基于归纳的递归算法(归纳的思想方法归纳的思想方法)(2)归纳法的思想方法归纳法的思想方法 对于一个规模为n的问题p(n),归纳法的思想方法是:n基础步:a1是问题p(1)的解。n归纳步:对所有的k,1kn,若b是问题p(k)的解,则p(b)是问题p(k+1)的解。其中,p(b)是对问题的某种运算或处理。例如。因为a1是问题p
3、(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)的解为止。这就是基于归纳的递归算法的思想方法。基于归纳的递归算法基于归纳的递归算法(选择排序)例5.1 基于递归的选择排序 假定要对n个元素的数组A进行排序,可以如下进行:n基础
4、步:当n=1时,数组A2n的最小者Aj,Aj与A1交换,A1有排序。n归纳步:如果A1n-1的n-1个元素已经排序,则An有序。算法算法5.1 SelectionSort 输入:输入:n个元素的数组A1n 输出:输出:按非降序排列数组A1n 1.sort(1)过程 sort(i)1 if in then 2 k=i基于归纳的递归算法基于归纳的递归算法(选择排序)3 for j=i+1 to n 4 if Aj1 then2x=Ai3sort(i-1)基于归纳的递归算法基于归纳的递归算法(插入排序)3j=i-1 4 while j0 and Ajx 5Aj+1Aj 6 j=j+1 7 end w
5、hile 8Aj+1=x 9 end if 最坏情况下时间复杂性算法分析最坏情况下时间复杂性算法分析:由基础步知:当n=1时,即只有一个元素已经有序,元素比较次数为0;当n1时,可由归纳步知,总比较次数C(n)为:)(nC10n1)1()1(nnnC)()1()1()(2211nnnnjjnCnjnj基于归纳的递归算法基于归纳的递归算法(整数幂)0,10,2222mxmmxxmxxmmmm为奇数为偶数例5.3 整数幂 用一个高效的方法求实数x的n次幂,其高效算法描述如下:算法算法 Exprec输入:输入:实数x和非负整数n输出:输出:1.power(x,n)过程:power(x,m)nx基于归
6、纳的递归算法基于归纳的递归算法(整数幂)1 if m=0 then y=12 else3 y=power(x,m/2)4 y=y25 if m为奇数 then y=xy6 end if7 return y最坏情况下时间复杂性算法分析最坏情况下时间复杂性算法分析:乘法次数C(n)为:)(nC00n022nnC)(log)(nnC例5.4 设有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+a0Pn(x)=x Pn-1(x)+a0由归纳知:基于归纳的递归算法基于归纳的递归算
7、法(n阶多项式)n基础步:当n=0时,有P0(x)=an。n归纳步:对于任意的k,1kn,如果前面k-1步已计算出pk-1:Pk-1(x)=anxk-1+an-1xk-2+an-k+2x+an-k+1 则有:Pk(x)=x Pk-1(x)+an-k 算法算法 HORNERERC 输入:输入:非负正数n,实数序列a0,a1,an和实数x 输出:输出:n次多项式Pn(x)=anxn+an-1xn-1+a1x+a0的值 1 hn(n,x)过程过程 hn(m,x)1 if m=0 then 2 return an 3 else 4 p=x*hn(m-1,x)+an-m 5 return p 6 end
8、 if基于归纳的递归算法基于归纳的递归算法(n阶多项式)基于归纳的递归算法基于归纳的递归算法(n阶多项式)最坏情况下时间复杂性算法分析最坏情况下时间复杂性算法分析:第4行中的乘法作为基本运算,总的乘法次数C(n)为:)(nC00n01)1(nnC)()(nnC空间复杂性算法分析空间复杂性算法分析:)()(nnS另外:另外:基于归纳的迭代算法参见课本算法5.6(P85)例5.5 求序列1,2,n的所有排列。假定序列已依次存放在数组A中,为了生成这n个元素的所有排列,可以采用下面步骤:(1)因A1=1,即排列的第一个元素为1,生成后面的n-1个元素的排列。(2)A1与A2互换,即排列的第一个元素为
9、2,生成后面的n-1个元素的排列。(3)如此下去,A1与An互换,即排列的第一个元素为n,生成后面的n-1个元素的排列。至此,为了生成后面n-1个元素的排列,继续采取下面的步骤:(1)因A2=2,即排列的第二个元素为2,生成后面的n-2个元素的排列。(2)A2与A3互换,即排列的第二个元素为3,生成后面的n-2个元素的排列。(3)如此下去,A2与An互换,即排列的第二个元素为n,生成后面的n-2个元素的排列。基于归纳的递归算法基于归纳的递归算法(排列)这种步骤继续,当排列的前n-2个元素已 确定后,为生成 后面2 个元素的排列,可以:(1)An-1=n-1,即排列的第n-1个元素为n-1,生成
10、后面的1个元素的排列。(2)An-1与An互换,即排列的第n-1个元素为n,生成后面的1 个元素的排列,此时A中的n个元素已构成一个排列。(3)如此下去,A2与An互换,即排列的第二个元素为n,生成后面的1个元素的排列,此时A中的n个元素已构成一个排列。由归纳法知:基于归纳的递归算法基于归纳的递归算法(排列)n基础步:当k=1时,数组只有一个元素,它已是一个排列。n归纳步:如果前面k-1个元素已是完成的排列,为了对后面的k个元素的排列,只要元素Ak与Aj逐一互换(k+1jn),每互换一次,调用算法perm(k)即可完成一个排列。于是,n个元素的全排列算法如下:基于归纳的递归算法基于归纳的递归算
11、法(排列)算法算法 Permutation1 输入:输入:数组A1n,正数n 输出:输出:数1,2,n的所有可能排列 1 for j=1 to n 2 Aj=j 3 end for 过程过程 perm1(m)1 if m=n then 2 output A1n 3 else 4 for j=m to n 5 Am与Aj互换 6perm1(m+1)7Am与Aj互换 8end for 9end if 基于归纳的递归算法基于归纳的递归算法(排列)最坏情况下时间复杂性算法分析最坏情况下时间复杂性算法分析:基本运算为迭代次数,第6行被调用n次,元素互换次数为2n次总的递归调用次数C(n)为:)(nC10
12、n12)1(nnnnC)!()(nnnC解得:另外:另外:第二种全排列算法参见课本算法5.8(P97)基于归纳的递归算法基于归纳的递归算法(寻找多数元素寻找多数元素)n寻找多数元素寻找多数元素 设A1n是一个整数序列和A中的元素a,如果a在A中出现的次数多于 n/2,则称a是A中的多数元素。如序列1,3,2,3,3,4,3中3是多数元素。那么,有哪些寻找多数元素的方法呢?寻找多数元素的方法:(1)蛮力方法:要花次 比较,才能确定A中是否有多数元素。(2)排序方法:最坏情况下,要花 次比较,才能确定A中是否有多数元素。(3)寻找中间元素方法:由课本6.5知,花次 比较,能确定A中是否有多数元素,
13、但它的常量太大,且方法复杂。综上所述,是否能用归纳法的思想,发现一个更好的寻找多数元素的方法,回答是肯定的。)(2n)log(nn)(n基于归纳的递归算法基于归纳的递归算法(寻找多数元素寻找多数元素)再次考察序列1,3,2,3,3,4,只比较9次就可以确定序列中的多数元素是3。n观察结论观察结论 在原序列中去除两个不同的元素后,那么在原序列中的多数元素还是多数元素。这个观察结论支持寻找多数元素的侯选者的过程。于是,在A1n寻找多数元素的侯选者的过程如下:(1)计数器置count=1,j=1,c=Aj。(2)重复直至j=n或count n/2 then return c 7 else retur
14、n none基于归纳的递归算法基于归纳的递归算法(寻找多数元素寻找多数元素)过程过程 candidate(m)1 j=m;c=Aj;count=1 2 while jn and count0 3j=j+1 4 if Aj=c then count=count+1 5 else count=count-1 6 end if 7 if j=n then return c 8 else return candidate(j+1)最坏情况下时间复杂性算法分析最坏情况下时间复杂性算法分析 (1)在过程candidate的第7步,当j=n时,即c是侯选者,至多比较n-1次,而第八步递归0次;而算法MAJORITY中的第四步比较次数为n。所以,总比较次数C(n)=。(2)在过程candidate的第7步,当jn时,即count=0,c不是侯选者,而第八步至多递归n/2次;而算法MAJORITY中的第四步比较次数为n。所以,总比较次数C(n)=。综上所述,算法MAJORITY总比较次数C(n)=。)(n)(n)(n