1、1,递归及递归算法分析,2,主要内容,递归的实现机制 递归算法编制 递归关系式求解,3,递归的实现机制,1.递归的概念 直接或间接地调用自身的算法称为递归算法。 用函数自身给出定义的函数称为递归函数。 直接调用自身的算法称为直接递归 间接调用自身的算法称为间接递归,4,由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。 分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。,5,主程序call A 1：,
2、2.子程序的内部实现原理 1）子程序调用的一般形式一次调用 N次调用 嵌套调用 平行调用,子程序A,主程序call A 1： call A 2：,子程序A,主程序call A 1：,子程序A 子程序B call B 2：,主程序call B 1：,子程序B call A 2：,子程序A,6,2）值的回传 实参和形参的数据传递 传值 实参的值不发生改变 传地址 实参的值发生改变 值的回传通常有两种形式： 两次传值方式：按照指定类型为变参设置相应的存储空间，在执行调用时，将实参值传送给变参在返回时将变参的值传给实参。 传地址：在内部将变参用一个地址替换，调用时，先执行地址传送，将实参地址传送给变参
3、，在执行过程中，对变参的操作实际变成对实参的操作。,7,3)子程序调用的内部操作 执行调用时，系统完成的操作 返回地址进栈，为子程序的局部变量开辟空间 为子程序准备数据：计算实参值，并将其值送给形参 转入子程序入口地址 返回时，系统完成的操作： 变参或函数的值保存到回传变量中 从栈顶取返回地址 返回调用程序 将回传变量的值送给实参,8,3.递归过程的内部实现原理 程序Aif 出口条件 then 简单语句else 简单语句；call A ； 1：简单语句；endif endA 递归程序的执行令人担心是否引发死循环。担心是多余的！ 因为每次调用，必有一些数据发生变化，直到出现一组数据终止递归。这组
4、数据就是递归出口。,执行到出口条件 开始出栈,9,递归举例,直接递归 proc fact（n）if n=0 then return 1else return n*fact(n-1),间接递归 proc p1(n)if n0 then if odd(n) then p1(n-1); print n;else p2(n-1);print n; proc p2(n)if n0 then if n mod 3=0 then p1(n-1)else p2(n-1) ,10,例1 阶乘函数 阶乘函数可递归地定义为：,边界条件,递归方程,边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，
5、才能在有限次计算后得出结果。,递归函数举例,11,递归函数举例,例2 Fibonacci数列 无穷数列1，1，2，3，5，8，13，21，34，55，被称为Fibonacci数列。它可以递归地定义为：,边界条件,递归方程,第n个Fibonacci数可递归地计算如下： public static int fibonacci(int n)if (n = 1) return 1;return fibonacci(n-1)+fibonacci(n-2);,12,递归函数举例,例3 Ackerman函数 当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。 Ackerman函数A(n，m
6、)定义如下：,13,例3 Ackerman函数 前2例中的函数都可以找到相应的非递归方式定义：,但本例中的Ackerman函数却无法找到非递归的定义。,14,例3 Ackerman函数 A(n，m)的自变量m的每一个值都定义了一个单变量函数： M=0时，A(n,0)=n+2 M=1时，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和A(1,1)=2故A(n,1)=2*n M=2时，A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，和A(1,2)=A(A(0,2),1)=A(1,1)=2，故A(n,2)= 2n 。M=3时，类似的可以推出 M=4时，A(n,4)的增
7、长速度非常快，以至于没有适当的数学式子来表示这一函数。,15,例3 Ackerman函数 定义单变量的Ackerman函数A(n)为，A(n)=A(n，n)。 定义其逆函数(n)为：(n)=minkA(k)n。即(n)是使nA(k)成立的最小的k值。 (n)在复杂度分析中常遇到。对于通常所见到的正整数n，有(n)4。但在理论上(n)没有上界，随着n的增加，它以难以想象的慢速度趋向正无穷大。,16,例4 排列问题 设计一个递归算法生成n个元素r1,r2,rn的全排列。,设R=r1,r2,rn是要进行排列的n个元素，Ri=R-ri。 集合X中元素的全排列记为perm(X)。 (ri)perm(X)
8、表示在全排列perm(X)的每一个排列前加上前缀得到的排列。R的全排列可归纳定义如下：,当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素； 当n1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，(rn)perm(Rn)构成。,N!,17,r1-t(1)=1 r1、r2-r1perm(R1) r2perm(R2) t(2)=2*t(1) r1、r2、r3 r1perm(R1) r2perm(R2) r3perm(R3) t(3)=3*T(2) t(n)=n*t(n-1),18,例5 整数划分问题 将正整数n表示成一系列正整数之和：n=n1+n2+nk， 其中
9、n1n2nk1，k1。 正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。 例如正整数6有如下11种不同的划分：6；5+1；4+2，4+1+1；3+3，3+2+1，3+1+1+1；2+2+2，2+2+1+1，2+1+1+1+1；1+1+1+1+1+1。,19,前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。 在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。,?,20,(3) q(n,n)=1+q(n,n-1); 正整数n的划
10、分由n1=n的划分和n1n-1的划分组成。,(4) q(n,m)=q(n,m-1)+q(n-m,m),nm1; 正整数n的最大加数n1不大于m的划分由n1=m的划分和 n1m-1 的划分组成。,(1) q(n,1)=1,n1; 当最大加数n1不大于1时，任何正整数n只有一种划分形式， 即,(2) q(n,m)=q(n,n),mn; 最大加数n1实际上不能大于n。因此，q(1,m)=1。,包含m的划分,不包含m,21,递归算法设计,用递归求解问题的3个要求： 问题的描述涉及规模 规模发生变化后，问题性质不改变 问题的解决有出口 proc f（参数表）if 递归出口 then 简单语句；else
11、简单语句；call f（参数表）；简单语句；endif endf,22,23,例6 Hanoi塔问题 设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则： 规则1：每次只能移动1个圆盘； 规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上； 规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。,24,在问题规模较大时，较难找到一般的方法，因此我们尝试用递归技术来解决这个问题。,当n=1时，问题比较简
12、单。此时，只要将编号为1的圆盘从塔座a直接移至塔座b上即可。 当n1时，需要利用塔座c作为辅助塔座。此时若能设法将n-1个较小的圆盘依照移动规则从塔座a移至塔座c，然后，将剩下的最大圆盘从塔座a移至塔座b，最后，再设法将n-1个较小的圆盘依照移动规则从塔座c移至塔座b。 由此可见，n个圆盘的移动问题可分为2次n-1个圆盘的移动问题，这又可以递归地用上述方法来做。由此可以设计出解Hanoi塔问题的递归算法如下。,例6 Hanoi塔问题,public static void hanoi(int n, int a, int b, int c)if (n 0)hanoi(n-1, a, c, b);m
13、ove(a,b);hanoi(n-1, c, b, a);,思考题：如果塔的个数变为a,b,c,d四个，现要将n个圆盘从a全部移动到d，移动规则不变，求移动步数最小的方案。,25,n=3 t(3)=7 n=4 t(4)=15 n=10 t(10)=1023 n=16 t(16)=65534,26,递归小结,优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。,27,递归算法的时间复杂度分析,递归函数求解 简单递归式求解 master method递推方程
14、的特征方程求解,28,public static void hanoi(int n, int a, int b, int c)if (n 0)hanoi(n-1, a, c, b);move(a,b);hanoi(n-1, c, b, a); T(n)=2T(n-1)+O(1) n10 n=0,T(n)=2n-1,4,29,简单递归式的求解,1.T(n)=T(n-1)+c1 n1c2 n=1 2. T(n)=2T(n/2)+c1 n 2c2 n2 3. T(n)=2T(n/2)+(n) n 2O(1) n2,30,T( n/2 ) + T( n/2 ) + 1 (n 1),0 (n = 1),
15、例1 T(n) =,解 ：T(n)=2T(n/2)+1=22T(n/22)+2+1=23T(n/23)+22+2+1令2r=n=2rT(1)+2r-1+。+2+1=(1-2r)/(1-2)=n-1 T( n ) = n - 1,31,解上述递推式：T( n ) = 3 T( n/2 ) + k n= 3 3 T( n/22 ) + k (n / 2 ) + k n=32T(n/22)+3k(n/2)+kn= =3rT(n/2r)+(3/2)r-1kn+.+kn=3rk+ (3/2)r-1kn+.+kn,= 3 r+1 k - 2 k n,= 3 k 3log2n - 2 k n 3 k n 1
16、.59 - 2 k n = O( n 1. 59 ),32,例3,T( n/2 ) + T( n/2 ) + (n - 1) (n 1),0 (n = 1),T(n) =,设：n = 2r （ r:非负整数）。,有：T(n) = 2 T(n/2 ) + ( n - 1 ),T(n/2) = 2 T(n/22 ) + (n/2 - 1),T(n/22) = 2 T(n/23 ) + (n/22 - 1), ,T(n/2r-1) = 2 T(n/2r ) + (n/2r-1 - 1),+),2 22 2,22 23 + 22,2r-1 2r 2r-1,T( n ) = 2r T(1) + rn -
17、 (2r-1 + 2r-2 + +20),= nlog2n - n +1 = O(nlog n),33,Master Method,T(n)=aT(n/b)+f(n) a1b1 f(n)是一个非负渐进函数 case1： 0,使f(n)=O(nlog ba-) 即00,c0,使f(n)= (nlog ba+) ,af(n/b)cf(n)则T(n)=(f(n),34,例1 T(n)=4T(n/2)+n a=4 b=2 f(n)=O(n2-)取=1则T(n)=(n2) 例2 T(n)=4T(n/2)+n2 a=4 b=2 f(n)= (n2lgnk)取K=0 则T(n)=(n2lgn) 例3 T(n
18、)=4T(n/2)+n3 a=4 b=2 f(n)=n3= (nlog ba+)取=1 且4f(n/2)=n3/2n3 取c=1 则T(n)=(n3),35,递推方程的特征方程求解,一、常系数线性递推方程的特征方程解法,1. 齐次常系数线性递推方程的特征方程解法,（1）定义：k阶齐次常系数线性递推方程:(R): H(n) = a1H(n - 1) + a2H(n - 2) + +akH(n - k)其中： 1）a1, a2, , ak为常数；2）ak 0, n k。,36,则(R)的通解是：H(n) = c1x1n + c2 x2n + + ck-e xk-en+ c k-e+1xpn + c
19、 k-e+2 n xpn + + ck ne-1 xpn,37,例 求Fibonacci序列的Fn,F(n) =,F(n - 1) + F(n - 2) (n 1),1 ( n = 1)0 ( n = 0),38,解：(R): F(n) = F(n -1) + F(n - 2),(E): x2 - x - 1 = 0,由 F(0) = 0 和F(1) = 1 知：,39,2 T( n - 1) + 2 T( n - 2 ) ( n 2 ),3 ( n = 1 ),8 ( n = 2 ),例 T( n ) =,(R): T( n ) = 2 T( n - 1) + 2 T( n - 2 ),(E
20、): x2 - 2x - 2 = 0,40,解：由： Sn = 12 + 22 + + n2 (1),递推：S n-1 = 12 + 22 + +(n - 1)2 (2),由（1）- （2） 得：Sn - S n-1 = n2 (3),对（3）递推：Sn-1 - Sn-2 = (n - 1)2 (4),由(3) - (4) 得：Sn - 2S n-1 + S n-2 = 2n - 1,(E): x4-4x3+6x2-4x+1=0 -(x - 1) 4 = 0,x1 = x2 = x3 = x4 = 1,5,41,因为特征方程的解是四重根，所以：Sn = c11n +c2 n 1n + c3 n
21、2 1n + c4 n3 1n= c1 + c2n + c3n2 + c4n3,由： S0 = 0, S1 = 1, S2 = 5, S3 = 14, 知：c1 = 0 , c2 = 1/6, c3 = 1/2, c4 = 1/3,所以：Sn = 1/6 n ( n + 1 ) (2 n + 1 ),42,2 非齐次常系数线性递推方程的特征方程解法,（1）定义：(R)为k阶非齐次常系数线性递推方程:(R): H(n) = a1H(n - 1)+a2H(n - 2)+ +akH(n - k)+f(n)其中： 1）a1, a2, , ak为常数；2）ak 0, n k, f(n) 0。,（2）（R
22、）的解结构：设：（R）的通解是H(n)，且它有一个特解H*(n)；而与（R)相对应的 齐次方程(R)的通解是H(n)。则有（R）的解：H(n) = H(n) + H*(n),43,(3) (R)的特解形式讨论,1）当f(n) 形如bnt( b0, t:非负整数）时，(R)的特解为：H*(n) = p1nt + p2nt-1+ + pt n + pt+1 其中：p1, p2, ， pt+1是待定系数。,但，当x = 1是(R)的 j 重特征根（j 1）时，其特解应改设为： H*(n) = p1nt+j + p2nt-1+j+ + pt+1nj,2）当f(n) 形如 b rn( b0, r 0 ）
23、时，(R)的特解为：H*(n) = p rn 其中：p是待定系数。,但，当 x = r 是(R) 对应的(R)的 j 重特征根( j 1)时，(R)的特解应改设为： H*(n) = p nj rn,44,T(n) =,2T( n - 1 ) + k (n 1) (k:正数）,k ( n = 1 ),解：(R) : T(n) = 2T(n - 1) + k,(R) : T(n) = 2T(n - 1),(E): x - 2 = 0 x = 2,(R)的通解： T(n) = c 2n,因为(R)中，f(n) = k,所以， 设： T*(n) = p,显然， T*(n - 1) = p,45,把T*
24、(n)、T*(n - 1)代入(R) ,有：p = 2p + k p = - k,故：T*(n) = - k,(R)的通解：T(n) = T(n) + T*(n) = c 2n - k,由T(1) = k, 把它代入上式， 有：2 c - k = k c = k,(R)的通解：T(n) = k( 2n - 1)= O( 2n ),46,例 T(n) =,2n-3 - T( n -2 ) ( n 4 ),1 ( n = 3 ),2 ( n = 4 ),解：(R): T(n) = - T(n - 2 ) + 2n-3,(R): T(n) = - T(n - 2 ),(E): x2 + 1 = 0,
25、(R) 的通解：T(n) = c1cos(n/2) + c2sin(n/2),（ 其中： = 1， = /2）,47,48,解：由： Sn = 12 + 22 + + n2 (1),递推：S n-1 = 12 + 22 + +(n - 1)2 (2),由（1）- （2） 得：Sn - S n-1 = n2 (R),(E): x - 1 = 0 x = 1,(R): Sn - S n-1 = 0,(R)的通解：Sn = c,设：(R)的特解是：S*n = p1n3 + p2n2 + p3n,代入(R), 得：p1 = 1/3, p2 = 1/2, p3 = 1/6,(R)的通解：Sn = p1n
26、3 + p2n2 + p3n + c,由S0 = 0,知：c = 0 故： Sn = p1n3 + p2n2 + p3n,49,变系数/非线性递推方程的求解原则：“变换”。,一、变“非线性”为“线性”,解：令：G(n) = H2(n),则有：,解上述递推式，得：G(n) =5 2n - 1,50,二、变“变系数”为“常系数”,51,整理、改写上述递推式：,由(1) - (2) 得：nT(n) - (n - 1)T(n - 1) = 2(n - 1) + 2T(n - 1),52,53,= ln n - ln 3,T(n) = (n + 1) Q(n) 2(n + 1) ln n + (b/2
27、- 1 - 2ln 3)(n +1) + 4,= O(n ln n),54,递归程序的阅读法,用图形方式描述执行轨迹 按次序写出程序在当前调用层上实际执行的语句，并用有向弧表明语句执行次序 对程序中的每个调用语句写出实际调用形式，在其下（右）边写出本次调用的子程序实际执行的语句，用有向弧指示。 被调用子程序执行完有向弧指向其上级（标上形参的值） 变参：再返回路线上增加语句实参=变参函数： 实参=函数值 最后，顺着有向弧的路径写出结果。,55,例,proc f(w)if w0 then f(w-1)print wf(w-1) end f,56,习题答案,答：T(n) = 2b nlog2n -
28、2b n + 3b = O(nlog2n),57,(1) 当 ac 时, 因为 ki 收敛于一个常数， T(n) = O(n),(2) 当 a=c 时， T(n) = bn(r+1) = bn (logcn + 1) = O(n log n),(3) 当 ac 时, T(n) = bn (kr+1 - 1) / (k-1) = bk / (k - 1) ar - bn / (k - 1)= bk/(k - 1) alogcn - bn/(k - 1) = O ( nlogca ),答：T(n) = 2n+1 - ( n + 2 ),58,答： T(n) = 10 4n - ( 3n + 10)
29、 3n,4. 试证：当特征方程(E)包含有二重根 x 1,2 = xp 时，齐次方程(R)通解包含有：T(n)= c1xpn + c2 n xpn,证：设：齐次常系数线性递推方程如下：H(n) = a1H(n-1) + a2H(n-2) + +akH(n-k) (R),它所对应的特征方程是： xk - a1xk-1 - a2xk-2 - - ak-1x - ak = 0 (E),59,对(E)两边同乘xn-k (x0)，有： xn - a1xn-1 -a2xn-2 - - a k-1xn-k+1 - ak xn-k = 0 (M),因为(E)有二重根x1 = x2 = xp， 所以(M)式可改
30、写成 (x - xp)2 f(x) = 0 (M),对式(M)左边求导，得到： nxn-1 - a1(n-1)xn-2 - a2(n-2)xn-3 - - ak-1(n-k+1)xn-k - ak(n-k)xn-k-1 (M),现证(M) 等于零：,可见， (M) 式实际上就是：2(x - xp) f(x) + (x - xp) 2 f (x) =(x - xp)2f(x) + (x - xp) f (x) (N),显然，当x = xp仍有(N)等于零。,60,也就是说，把x = xp代入(M) ，应当有下式成立：nxpn-1 - a1(n-1)xpn-2 - a2(n-2)xpn-3 - - ak-1(n-k+1)xpn-k - ak(n-k)xpn-k-1 = 0,上式两端同乘以xp（xp 0），有： nxpn - a1(n-1)xpn-1 - a2(n-2)xpn-2 - - ak-1(n-k+1)xpn-k+1- ak(n-k)xpn-k = 0,(M) 等于零，证毕。,此式说明， x = nxp是(R)的一个解。,易证， x = xp是(R)的另一个解。,综上，特征方程(E)包含有二重根 x 1,2 = xp 时，齐次方程(R)通解包含有：T(n) = c1xpn + c2 n xpn，证毕。,
