递归及归纳法课件.pptVIP

（1）递归 递归是一种十分重要的程序设计方法，对于一些问题，用递归方法设计算法可使算法简洁明了，逻辑清晰，易于设计。 递归指算法自己调用自己, 相应的算法称为递归算法。 递归分类：直接递归与间接递归 递归方法：解决一类满足递归关系的问题。 递归本质：对原问题的求解可转化为对其性质相同的 子问题的求解。 ;基于归纳的递归算法(递归概念);基于归纳的递归算法(归纳的思想方法);基于归纳的递归算法(选择排序);基于归纳的递归算法(选择排序);基于归纳的递归算法(插入排序);基于归纳的递归算法(插入排序);基于归纳的递归算法(整数幂);基于归纳的递归算法(整数幂);例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+ a0 Pn(x)=x Pn-1(x) + a0 由归纳知： ; 算法 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 if; ;例5.5 求序列1，2，?，n的所有排列。假定序列已依次存放在数组A中，为了生成这n个元素的所有排列，可以采用下面步骤： (1) 因A[1]=1，即排列的第一个元素为1，生成后面的n-1个元素的排列。 (2) A[1]与A[2]互换，即排列的第一个元素为2，生成后面的n-1个元素的排列。 (3)如此下去， A[1]与A[n]互换，即排列的第一个元素为n，生成后面的n-1个元素的排列。 至此，为了生成后面n-1个元素的排列，继续采取下面的步骤： (1) 因A[2]=2，即排列的第二个元素为2，生成后面的n-2个元素的排列。 (2) A[2]与A[3]互换，即排列的第二个元素为3，生成后面的n-2个元 素的排列。 (3)如此下去， A[2]与A[n]互换，即排列的第二个元素为n，生成后面的n-2个元素的排列。;这种步骤继续，当排列的前n-2个元素已 确定后，为生成 后面2 个元素的排列，可以： (1) A[n-1]=n-1，即排列的第n-1个元素为n-1，生成后面的1个元素的排列。 (2) A[n-1]与A[n]互换，即排列的第n-1个元素为n，生成后面的1 个元素的排列，此时A中的n个元素已构成一个排列。 (3)如此下去， A[2]与A[n]互换，即排列的第二个元素为n，生成后面的1个元素的排列，此时A中的n个元素已构成一个排列。 由归纳法知：;基于归纳的递归算法(排列); ;基于归纳的递归算法(寻找多数元素);基于归纳的递归算法(寻找多数元素);基于归纳的递归算法(寻找多数元素);基于归纳的递归算法(寻找多数元素)