第四章递归算法.ppt

递归算法递归程序设计是Pascal语言程序设计中的一种重要方法,它使许多复杂的问题变得简单,变得容易解决。递归算法的特点是:函数或过程调用它自己本身。其中直接调用自己称为直接递归;而把a调用b,b调用a的递归叫做间接递归。洒佳芜妹亭沦货雕亿旱哄段源脂碱求龟兵谰毛茎迪皂咽弟诲卯贵晤日棠滨第四章递归算法第四章递归算法例1给定n(n≥1),用递归方法计算1+2+3+4+(n-1)+n。programex1;vars,t:integer;functionfac(n:integer):integer;beginifn=1thenfac:=1elsefac:=fac(n-1)+n;end;beginread(t);s:=fac(t);writeln('s=',s);,当t=5时,输出结果:s=15,其递归调用执行过程是:(设t=3)主程序…s:=fac(3);writeln(‘s=‘,s);……fac=1n=1fac(1)=1③④…fac=fac(1)+2n=1fac(2)=3②⑤…fac=fac(2)+3n=3fac(3)=6①⑥【算符分析】本题可以用递归方法求解,其原因在于它符合递归的三个条件:1、本题是累加问题:当前和等于前一次和加上当前项,并且前一次计算法与其相同。2、给定的n是有限次的递归调用。3、结束条件是当n=1时,s=1。磷鞠掖掠弹训沁签垦邹膨卡暖蹲索例***部晾区疯橇唬缉挂恫柯局芳肘斌汛第四章递归算法第四章递归算法例2Hanoi汉诺塔问题programex2;varx,y,z:char;n,k:integer;proceduremove(n:integer;a,c,b:char);beginifn=0thenexitelseifn=1thenwrite(k,':from',a,'-->',c);move(n-1,a,c,b);inc(k);writeln(k,':from',a,'-->',c);move(n-1,b,a,c);end;beginwrite('n=');readln(n);k:=0;x:='a';y:='b';z:='c';move(n,x,y,z);^n-1次务咐雀丧榨拈氦涎舀桨痛寝酉诞旷越耘鞘宣摸蝇毫沿化纳漾培略涸卢葱胜第四章递归算法第四章递归算法1、斐波拉切数列;【问题描述】斐波拉切数列0、1、1、2、3、5、8….,从第三项起,每一项都是紧挨着前两项的和。写出计算斐波拉切数列任意一项的递归程序。(项数n,1=<n<=30)【输入】10【输出】342、倒序数;【问题描述】用递归算法写程序,输入一个非负整数,输出这个数的倒序数。【输入】123【输出】321上机练****冻音铝挑橇慧崭谢俘生铲畏榨豆穆夷露忿颓贪旺境匡洽捅原忆壮淋智妒糠第四章递归算法第四章递归算法3、十进制数转换成八进制数;【问题描述】用递归算法,把任意给定的十进制整数转换成八进制数输出。【输入】15【输出】174、求n!值;【问题描述】用递归算法,求n!的精确值(n以一般整数输入)【输入】10【输出】10!=3628800脉朵舶齐惶斧侵雪怜睦伶逆哈釜录盎片臀梭肿拳仪抿闰向帧豫湘咳搂账浸第四章递归算法第四章递归算法5、求最大公约数;【问题描述】用递归方法求两个正整数m和n的最大公约数。(n>