数据结构递归算法ppt课件.ppt

递归算法(Recursion),本章内容递归算法定义递归算法举例递归算法复杂性的计算,递归(Recursion)定义,直接或间接地调用自身的算法称为递归算法直接或间接调用自身的函数称为递归函数尾递归是指递归调用的语句在递归函数的最后一句递归算法的特点：用于解决一类递归定义的问题算法易于实现，简单明了,递归算法：,1 (n=0,1)n! = n(n-1)！ (n1),函数的递归调用,1. 定义： 在调用一个函数的过程中直接或间接地调用该函数本身。直接调用int f(x)int x; int y,z; . z=f(x); return (2*z); ,f 函数,调用 f函数,int f1(x)int x; int y,z; . z=f2( y); return (2*z); ,int f2(t)int t; int a,c; . c=f1(a); return (3+c); ,间接调用,特点 是无终止的递归调用，因此，应该给定一个限制递归次数的条件。,float fac ( int n) float f; if(n0) printf(“n0,data error!n”); else if(n= =0|n= =1) f=1; else f=fac(n-1)* n ; return f; ,例如：写一函数求n!,以求4的阶乘为例：,fac(4)=4*fac(3),fac(3)=3*fac( 2),fac(2)=2*fac( 1),fac(1)=1,fac(4)=4*3*2*1,fac(2)=2*1,fac(3)=3*2*1,下推,回代,利用栈实现递归调用,递归的执行情况分析,long Fact ( int n) long s; if ( n= =1) s=1;else s=n*Fact(n-1); return(s);,使用递归的准则,如果待解决的问题具备下列两个特性，就可以考虑使用递归。1)复杂的问题可以转换为简单些的1个或几个子问题；2)最简单的问题可以直接解决,例1.3斐波那契(Fibonacci)序列： F0= F1 = 1 Fi = Fi-1 + Fi-2 （i1) 算法 求斐波那契数 procedure F(n) /返回第n个斐波那契数/ integer n if n 1 then return(1) else return(F(n-1) + F(n-2) endif end F算法效率：对F(n-1) 、F(n-2)存在大量的重复计算 ，可以改进算法：保存中间结果,例1.4 欧几里得算法 已知两个非负整数a和b，且ab0，求这两个数的最大公因数。 辗转相除法：若b=0，则a和b的最大公因数等于a；若b0，则a和b的最大公因数等于b和用b除a的余数的最大公因数。 算法1.8 求最大公因数 procedure GCD(a,b) / 约定ab / if b=0 then return(a) else return (GCD(b,a mod b) endif end GCD 例： GCD(22,8) = GCD(8,6) = GCD(6,2) = GCD(2,0) = 2;,例1.5 递归在非数值算法设计中的应用 已知元素x，判断x是否在A（1：n）中。 算法 在A（1：n）中检索x procedure SEARCH(i) /如果在A（1：n）/中有一元素A（k）=x，则将其第一次出现的下标k返回，否则返回0/ global n,x,A(1:n) case :in: return(0) :A(i) = x; return(i) :else: return(SEARCH(i+1) endcase end SEARCH,子程序的调用形式,STACK,2.递归算法设计,定义递归（数学公式，数列等的定义。）数据结构递归（单链表，树，二叉树）可用递归解决的问题P（hanoi问题） 问题P具有大规模不同规模的问题P，具有相同性质；并且大规模的问题由小规模的问题构成小规模的问题是可解的关键：找到递归的递推关系找到结束递归的条件,递归求解的伪代码,rocedure P(参数表)beginif 满足递归出口then 简单操作elsebegin 简单操作; CALL P; 简单操作; end;endendp,简单的0/1背包问题,设一个背包容纳的物品最大质量为m,现有n件物品，质量为m1,m2, ,mn,均为正整数。要求从中挑选若干件，使背包质量之和正好为m.（在此问题中，第i件物品要么取，要么不取，不能取一部分，故问题可能有解，可能无解）设用knap(m,n)来表示此问题。有解为true,否则为false,先考虑将物品mn放入背包的情况：knap(m,n) = 若mn = m , 则knap(m,n) true若mn m,则knap(m,n) knap(m,n-1) 即放弃mn物品，从n-1中选取否则mn m， 则knap(m,n) knap(m,n-1) knap(m-mn,n-1)即如果选中mn，问题转化为knap(m-mn,n-1)是否有解；如果无解，放弃mn物品问题转化为knap(m,n-1) 是否有解。,bool knap(m,n)if( n = 1 ) /出口条件if( m1 = m ) return true;else return false;if( mn = m ) return true;if( mn m ) return knap(m,n-1);if( knap( m-mn,n-1 ) return true;return knap(m,n-1);,棋子移动,问题描述：有2n（n3）个棋子排成一行，白子用0代表，黑子用1代表。n=5的状态为： 0000011111_ _ (右边至少两个空位)移动规则：(1)每次必须移动相邻的两个棋子，这两个棋子不能互换位置(2)移动的颜色不限，移动的方向不限要求：最后成为 _ _ 0101010101 的状态(中间无空格)。,N=4,(4,5)-(9,10) n=6, (6,7)-(13,14) (8,9)-(4,5) (11,12)-(6,7) (2,3)-(8,9) n=5 (7,8)-(2,3) (1,2)-(7,8)N=5, (5,6)-(11,12) (9,10)-(5,6) n=4由数学归纳法可知；递归出口为n=4,如果2n个棋子的移动用chess(n)则递归关系 move（n,n+1)(2n+1,2n+2) move (2n-1,2n)(n,n+1) chess( n-1),空格在任何地方都是可等价变换的问题规模为n和为n-1有相似的地方吗？000000111111_ _ (问题的规模n)0000011111_ _01 (问题的规模 n-1,?)结论：(1)规模为n的问题可以通过两步的移动变成规模为n-1的问题!(2)初值（递归的结束条件n=?可以解）,1.初值的判断：n=2, 0011_ _ 0_ _ 101 010_ _ 1 , 无解n=3, 无解n=4:,0 0 0 0 1 1 1 1 _ _0 0 0 _ _ 1 1 1 0 10 0 0 1 0 1 1 _ _ 10 _ _ 1 0 1 1 0 0 10 1 0 1 0 1 _ _ 0 1_ _ 0 1 0 1 0 1 0 1,2.递推关系式:0 0 0 . . . 0 0 0 1 1 1 . . . 1 1 1 _ _ (n)0 0 0 . . . 0 0 _ _ 1 1 . . . 1 1 1 0 10 0 0 . . . 0 0 1 1 1 1 . . . 1 _ _ 0 1 (n-1)对n-1个棋子进行递归的移动直到n=4为止,3.算法实现：(对棋子的位置进行编号，从1,2,2n,2n+1,2n+2)void chess(int n) /n为移动的棋子数，n4 if( n = 4 ) /递归出口 else if( n4 ) /进入递归 move_to(n,n+1, 2n+1,2n+2); move_to(2n-1,2n,n,n+1); chess(n-1); ,4.思考：如果棋子的移动规则改为每次移动相邻的3个(4,5,)棋子，其他条件不变，则如何解决此问题？递归关系式的推导初值的判断(n=?有解)算法的实现,Hanoi塔问题,汉诺塔（Tower of Hanoi）游戏据说来源于布拉玛神庙。游戏的装置如图所示（图上以3个金片例），底座上有三根金的针，第一根针上放着从大到小64个金片。游戏的目标是把所有金片从第一根针移到第三根针上，第二根针作为中间过渡。每次只能移动一个金片，并且大的金片不能压在小的金片上面。该游戏的结束就标志着“世界末日”的到来。,分析：,游戏中金片移动是一个很繁琐的过程。通过计算，对于64个金片至少需要移动 264 1 = 1.61019 次 。,不妨用A表示被移动金片所在的针（源），C表示目的针，B表示过渡针。对于把n（n1）个金片从第一根针A上移到第三根针C的问题可以分解成如下步骤：,（1）将n-1个金片从A经过C移动到B。,（2）将第n个金片移动到C。,（3）再将n-1个金片从B经过A移动到C。,这样就把移动n个金片的问题转化为移动n-1个金片的问题，即移动n个金片的问题可用移动n-1个金片的问题递归描述，以此类推，可转化为移动一个金片的问题。显然，一个金片就可以直接移动。,void hanoi(int n, int a, int b, int c) if (n 1) hanoi(n-1, a, c, b); move(n,a,b); hanoi(n-1, b, a, c); else move(n,a,b); /结束条件 ,n个元素的全排列,N=1, 输出 1N=2, 输出 1,2 2,1N=3, 输出 1,2,3 1,3,2 2,1,3 2,3,1 3,1,2 3,2,1,解决：递推关系式初始值(递归的出口)算法实现,a = 1,2.3,4,n;/对ak an 进行全排列void Range(a,k,n) if( k = n ) Print(a); /输出排列 else for(i=k;in;i+) ak ai; /交换值 Range(a,k+1,n); /递归排列剩下的元素 ai ak; /交换值 初始调用： Range(a,0,n);,3.递归关系式的计算,递归算法时间复杂度的分析递归算法时间复杂度的计算,递归算法时间复杂度分析,根据递归算法思想，可以得到递归算法的时间复杂度的递推关系式求解递推关系式即可,例：一个楼有n个台阶，有一个人上楼有时一次跨一个台阶，有时跨2个台阶。问此人共有几种不同的上楼方法，并分析算法的时间复杂度。解：设H(n)为上楼的方法总数，则：当n=1, H(1) = 1当n=2, H(2) = 2当n2时, H(n) = H(n-1) + H(n-2)下面分析时间复杂度：设为T(n),T(n) 2T(n-1) 22T(n-2) 2n-1T(1) = O(2n),时间复杂度的计算-迭代法,T(n) = 2T(n/2) +cn = 2(2T(n/4) +c*n/2) +cn = 22T(n/4) + cn + cn = 23T(n/23) + cn + cn +cn = = 2kT(n/2k) + cn + cn + + cn = 2k*0 + kcn = cnlog2n = O(nlogn),K个,设 n/2k = 1,则 k = log2n,求O(T(n)=?,recursion tree （递推树、迭代树）,汉诺塔（Tower of Hanoi）问题：假设move所需的时间为1，则其时间复杂度：,T(n) = 2T(n-1) + 1 = 2 2T(n-2)+1 + 1 = 22T(n-2) + 2 + 1 = 23T(n-3) + 22 + 2 + 1 = = 2n-1T(1) + 2n-2 + + 23 + 22 + 2 + 1 = 2n-1 + 2n-2 + + 23 + 22 + 2 + 1 = 2n -1,若有64个圆盘，则需要移动264-1 = 1.61019次,T(n) = 2T(n-1) + n = 2 2T(n-2)+n-1 + n = 22T(n-2) + 2(n-1) + n = 23T(n-3) + 22(n-2) + 2(n-1) + n = = 2n-1T(1) + 2n-2*2 + + 23(n-3) + 22(n-2) + 2(n-1) + n = 2n-1+ 2n-2*2 + + 23(n-3) + 22(n-2) + 2(n-1) + n,求O(T(n)=?,T(n) = 2n-1+ 2n-2 + + 23 + 22 + 2 + 20 + 2n-2 + + 23 + 22 + 2 + 20 + + 22 + 2 + 20 + 2 + 20 + 20 = (2n-1) + (2n-1-1) + + (22-1) + (2-1) = 2n+1 -2 n = O(2n),作业,1.写出的递归求解算法。2.求O(T(n) = ?,