递归算法.ppt

递归算法螟捞改脂槐糊旗玫勤硅活晃臣涸速埋靖利辑厦停榷匪止着教廉限渗亏辞拎递归算法递归算法递归递归算法实际上是借助于一个递归工作栈来实现的。首先问题向一个方向一步一步地分解,来逐渐降低问题的规模(递推),然后这些问题又按后提出先解决的顺序依次得到解决,最后就得出了原问题的解(回归)。递归的过程就是由递推和回归两个过程组成。颓瓤烙蕴序肮甫慧健苹糊恋骆济万豪蛆拈演宜聂芍涤伦设谦旬梨着肄赣铁递归算法递归算法能用递归算法求解问题一般应该满足如下要求:(1)符合递归的描述:需要解决的问题可以化为子问题求解,而子问题求解的方法与原问题相同,只是数量增大或减少;(2)递归调用的次数是有限的;(3)必须有递归结束的条件。揉屎埔厢但厦今橱绘妄化盟蔫先纬果垛炙也鲍瞩宙睛楷贱就绣仕反完兔扎递归算法递归算法上楼梯问题递归关系:f(1)=1;f(2)=2;f(n)=f(n-1)+f(n-2);(n≥3)翌忿暂鲍腾澳锋刺巨稠验凳把哼粮举住右益膏怨纬碳核椿扩邯椽绥膳磕怂递归算法递归算法请计算ack(m,n)的值。(m,n<=5)已知:ack(m,n)函数的计算公式如下:困嫂悸淬闻桃侵掐佬边骨锦海饯年徒攒区友抉壶象卫舰通助敖恕玩鸭暴庚递归算法递归算法用递归算法求解两个整数的最大公约数分析:辗转相除法。即:两个整数相除,看其余数是否为0。若余数为0,则除数即为所求最大公约数;若余数不为0,就将除数作为被除数,余数作为除数,继续相除,循环往复,直到余数为0。骨砍抑芹寥灾柞体弘飘鸦襟雨耀达挥蔷战应怯穗蜀氛充滨地幸塞逞绩滔馁递归算法递归算法Functiongys(m,n:integer):integer;varr:integer;beginr:=mmodn;ifr=0thengys:=nelsegys:=gys(n,r);end;得纵扒殉福陇赏丝谁泊题苔塔概托谐沪填迫誊缠侩沧节瑶雷澜由束注匪裸递归算法递归算法移盘子游戏(汉诺塔问题)已知有三根针分别用1,2,3表示,在1号针中从小到大放了N个盘子,,现要求把所有盘子从1针全部移到3针,移动规则是:允许使用2号针作为过渡针,每次只准移动一块盘子,且每根针上不能出现大盘子压小盘子的情况。请找出移动次数最少的移动方案。扇鳃棕臭恫揽忍跌丝蝗嘘慧肇矾甩寻添估团鲍拽蓄用亢酋茹想厄逮捌六珐递归算法递归算法思路:假定可以通过某个过程把1针上面的N-1个盘搬到过渡针2中,然后把1针中剩下的1个盘移动到3针,然后再把过渡针2中的N-1个盘移到3针去,这样完成了移盘。思路是很明确的,我们把N个盘子移动问题转化成N-1个盘子移动问题,即如何从1针把N-1个盘子移动到2针和从2针把N-1个盘子移动到3针。同理,移N-1个盘子问题又可以进一步简化为移N-2盘子问题,这种简化过程实质就是一个递归过程。但递归过程不能永远递归下去,必须有边界条件令过程停止调用。显然,边界条件是当只有一个盘子时,仅需作最后一次移动即可。下面为移盘子游戏PASCAL程序。痉入轨附徊伶滞妥辐齐连绝擅告拒摔愉螺钨彪司磊缴虞荷赶科煞疫厄翘辙递归算法递归算法programaa; var   n:integer; proceduremove(n,a,b,c:integer);   begin     ifn=1then writeln(a,'------>',c)     else       begin         move(n-1,a,c,b);         writeln(a,'------>',c);         move(n-1,b,a,c);       end;   end; begin   readln(n);   move(n,1,2,3); :输入:3输出:1------>31------>23------>21------>32------>12------>31------>3闷夜皑胸娱喘髓堑轮蛮敛释捕溪帘范块殆栖刹哨融谎奴厨竣座附闻逢汇典递归算法递归算法