《第二十七讲递程序设计之递归2》由会员分享，可在线阅读，更多相关《第二十七讲递程序设计之递归2（18页珍藏版）》请在金锄头文库上搜索。
1、程序设计之递归（程序设计之递归（2 2）第二十七讲第二十七讲1 1试用递归的方法完成下列问题(2).(2).有一对雌雄兔有一对雌雄兔, ,每两个月就繁殖雌雄各一对兔子每两个月就繁殖雌雄各一对兔子. .问问n n个月个月后共有多少对兔子后共有多少对兔子? ? 分析：我们先模拟出前十个月的兔子对数分析：我们先模拟出前十个月的兔子对数1 1 2 3 5 8 13 1 1 2 3 5 8 13 我们的出结论：第我们的出结论：第N N天的兔子数等于天的兔子数等于N-1N-1天的兔子数目天的兔子数目+(n-+(n-2)2)天的老兔子繁殖的小兔子，即递推公式等于：天的老兔子繁殖的小兔子，即递推公式等于：AN
2、=AN-1+AN-2 N=3;AN=AN-1+AN-2 N=3;AN=1;(N=1)AN=1;(N=1)AN=1;(N=2)AN=1;(N=2)2 2参参参参考考考考程程程程序序序序Program ck(input,output);Program ck(input,output);VarVarDay:integer;Day:integer;Function tz(n:integer):integer;Function tz(n:integer):integer;BeginBeginIf n=1 then tz:=1If n=1 then tz:=1Else If n=2 then tz:=1E
3、lse If n=2 then tz:=1Else tz:=tz(n-1)+tz(n-2);Else tz:=tz(n-1)+tz(n-2);End;End;BeginBeginWriteln(Writeln( please input the dayplease input the day ););Readln(day);Readln(day);While day=0 doWhile day=0 doReadln(day);Readln(day);Writeln(tz(day);Writeln(tz(day);End.End.3 3回顾递归算法概念回顾递归算法概念 【递归的定义递归的定义递归
4、的定义递归的定义】 为了描述问题的某一状态，必须用到它的上一状态，而描述上一状为了描述问题的某一状态，必须用到它的上一状态，而描述上一状态，又必须用到它的上一状态态，又必须用到它的上一状态这种用这种用自已来定义自己自已来定义自己自已来定义自己自已来定义自己的方法，称为的方法，称为递归定义。递归定义。例如：定义函数例如：定义函数f(n)f(n)为：为： 则当则当n0n0时，须用时，须用f(n-1)f(n-1)来定义来定义f(n),f(n),用用f(n-1-1)f(n-1-1)来定义来定义f(n-1)f(n-1)当当n=0n=0时，时，f(n)=1f(n)=1。 由上例我们可看出，由上例我们可看出
5、，递归定义有两个要素：递归定义有两个要素： （1 1）递归边界条件递归边界条件递归边界条件递归边界条件。也就是所描述问题的最简单情况，它本身不。也就是所描述问题的最简单情况，它本身不再使用递归的定义。再使用递归的定义。 如上例，当如上例，当n=0n=0时，时，f(n)=1f(n)=1，不使用，不使用f(n-1)f(n-1)来定义。来定义。 （2 2）递归定义递归定义递归定义递归定义：使问题向边界条件转化的规则。递归定义必须能使问题向边界条件转化的规则。递归定义必须能使问题越来越简单。使问题越来越简单。 如上例：如上例：f(n)f(n)由由f(n-1)f(n-1)定义，越来越靠近定义，越来越靠近
6、f(0),f(0),也即边界条件。最简也即边界条件。最简单的情况是单的情况是f(0)=1f(0)=1。 4 4二、递归算法用于解决的问题n n一般来说，能够用递归解决的问题应该满足以下三个条件：1.需要解决的问题可以化为一个或多个子问题需要解决的问题可以化为一个或多个子问题需要解决的问题可以化为一个或多个子问题需要解决的问题可以化为一个或多个子问题来求解，而这些子问题的求解方法与原来的来求解，而这些子问题的求解方法与原来的来求解，而这些子问题的求解方法与原来的来求解，而这些子问题的求解方法与原来的问题完全相同，只是在数量规模上不同；问题完全相同，只是在数量规模上不同；问题完全相同，只是在数量规
7、模上不同；问题完全相同，只是在数量规模上不同；2.递归调用的次数必须是有限的；递归调用的次数必须是有限的；递归调用的次数必须是有限的；递归调用的次数必须是有限的；3.必须有结束递归的条件（边界条件）来终止必须有结束递归的条件（边界条件）来终止必须有结束递归的条件（边界条件）来终止必须有结束递归的条件（边界条件）来终止递归。递归。递归。递归。5 5二、递归算法用于解决的问题n n可用递归解决的具体问题：1.数据的定义形式是按递归定义的。如阶乘。数据的定义形式是按递归定义的。如阶乘。2.问题的解法按递归算法实现。如回溯算法。问题的解法按递归算法实现。如回溯算法。3.数据结构的形式是按递归定义的。如
8、树的遍历。数据结构的形式是按递归定义的。如树的遍历。function jc(n: integer): longint;function jc(n: integer): longint;beginbegin if (n = 0) then jc := 1 if (n = 0) then jc := 1 else jc := n * jc(n- else jc := n * jc(n-1);1);end;end;procedure m-search(t: node)procedure m-search(t: node)beginbegin if (t nil) then if (t nil) th
9、en begin begin m-search(t.left); m-search(t.left); visit(t); visit(t); m-search(t.right); m-search(t.right); end; end;end;end;6 6三、递归算法的执行过程Fac(5)5*Fac(4)4*Fac(3)3*Fac(2)2*Fac(1)1*Fac(0)1=1=1=2=6=24主程序=1207 7三、递归算法的执行过程Fac(5)n*Fac(4)n*Fac(3)n*Fac(2)n*Fac(1)n*Fac(0)1=1=1=2=6=24主程序=120n=5，retaddr=6n=4
10、，retaddr=6n=3，retaddr=6n=2，retaddr=6n=1，retaddr=6n=0，retaddr=61:function jc(n: integer): longint;1:function jc(n: integer): longint;2:begin2:begin3: if (n = 0) then3: if (n = 0) then4: jc := 14: jc := 15: else5: else6: jc := n * jc(n-1);6: jc := n * jc(n-1);7:end;7:end;8 8 例例3：求m与n的最大公约数。问题分析问题分析问题分
11、析问题分析： 从数学上可以知道求从数学上可以知道求mm与与n n的最大公约数等价于示的最大公约数等价于示n n与（与（m MOD nm MOD n）的最大公约）的最大公约数。这时可以把数。这时可以把n n当作新的当作新的mm，（，（m MOD nm MOD n）当作新的）当作新的n n，问题又变成了求新的，问题又变成了求新的mm与与n n的最大公约数。它又等价于求新的的最大公约数。它又等价于求新的n n与（与（m MOD nm MOD n）的最大公约数）的最大公约数如此继续，直如此继续，直到新的到新的n=0n=0时，其最大公约数就是新的时，其最大公约数就是新的mm。 例如求例如求2424与与1
12、616的最大公约数，等价于求的最大公约数，等价于求1616与（与（24 MOD 1624 MOD 16）的最大公约数，即）的最大公约数，即求求1616与与8 8的最大公约数。它又等价于求的最大公约数。它又等价于求8 8与（与（16 MOD 816 MOD 8）的最大公约数，即求）的最大公约数，即求8 8与与0 0的的最大公约数。此时最大公约数。此时n=0n=0，最大公约数就是，最大公约数就是8 8（边界条件）。（边界条件）。 这样我们可以得出递归模型为：这样我们可以得出递归模型为： 其中其中Gcd(m,n)Gcd(m,n)代表求代表求mm与与n n的最大公约数。的最大公约数。9 9参考程序参考
13、程序 Var Var m,n,g:integer;m,n,g:integer; function gcd(m,n:integer):integer;function gcd(m,n:integer):integer; beginbegin if n=0 then if n=0 then gcd:=mgcd:=melse else gcd:=gcd(n,m MOD n);gcd:=gcd(n,m MOD n); end; end; beginbeginread(m,n);read(m,n);g:=gcd(m,n);g:=gcd(m,n);writeln(m=,m,n=,n,gcd=,g);wri
14、teln(m=,m,n=,n,gcd=,g); end. end. 边界边界条件条件递归递归公式公式在主程序中在主程序中调用递归函数调用递归函数GCD(24,16)GCD(16,8)GCD(8,0)边界条边界条件，递件，递归成立归成立1010 递归算法适用的一般场合为递归算法适用的一般场合为 1. 1. 数据的定义形式按递归定义数据的定义形式按递归定义. . 如裴波那契数列的定义如裴波那契数列的定义: f(n)=f(n-1)+f(n-2); f(0)=1; : f(n)=f(n-1)+f(n-2); f(0)=1; f(1)=2. f(1)=2. 对应的递归程序为对应的递归程序为: : Fun
15、ction fib(n : integer) : integer; Function fib(n : integer) : integer; Begin Begin if n = 0 then fib := 1 if n = 0 then fib := 1 递归边界递归边界 else if n = 1 then fib := 2 else if n = 1 then fib := 2 递归边界递归边界 else fib := fib(n-2) + fib(n-1) else fib := fib(n-2) + fib(n-1) 递归递归 End; End; 这类递归问题可转化为递推算法这类递归
16、问题可转化为递推算法, , 递归边界作为递推的边界条件递归边界作为递推的边界条件. . 2. 2. 数据之间的关系数据之间的关系( (即数据结构即数据结构) )按递归定义按递归定义. . 如树的遍历如树的遍历, , 图的图的搜索等搜索等. . 3. 3. 问题解法按递归算法实现问题解法按递归算法实现. . 例如回溯法等例如回溯法等. . 1111下列递归函数和递归过程的执行结果是什么？(1)function f1(m:integer):integer;(1)function f1(m:integer):integer;beginbegin if m=0 then f1:=3if m=0 the
17、n f1:=3else f1:=else f1:=f1(m-1)f1(m-1)+5;+5;end;end;执行执行Writeln(f1(3):Writeln(f1(3):4 4););F1(3)=F1(2)+5=F1(1)+5+5=F1（0）+5+5+53+5+5+51212题目二(2)procedure p1(n:integer);(2)procedure p1(n:integer);var i:integer;var i:integer;beginbeginif if n0 n0 then beginthen beginfor i:=1 to n do for i:=1 to n do w
18、rite(n:3);write(n:3);writeln;writeln;p1(n-1);p1(n-1);end;end;end;end;调用调用p1(4);p1(4);1313题目三(3)procedure p2(n:integer);(3)procedure p2(n:integer);var i:integer;var i:integer;beginbeginif n0 then beginif n0 then beginp2(n-1);p2(n-1);for i:=1 to n do for i:=1 to n do write(n:3);write(n:3);writeln;writ
19、eln;p2(n-1);p2(n-1);end;end;end;end;调用调用p2(4);p2(4);1414题目四procedrue p3(n:integer);procedrue p3(n:integer);var i:integer;var i:integer;beginbeginif n0 then beginif n0 then beginfor i:=1 to n do write(i:3);for i:=1 to n do write(i:3);writeln;writeln;p3(n-1);p3(n-2);p3(n-1);p3(n-2);end;end;end;end;P3(
20、4)P3(4)1515第五题第五题( (5)procedure p4(n:integer);5)procedure p4(n:integer);var i:integer;var i:integer;beginbeginif0 then beginif0 then beginfor i:=1 to n do write(n:3);for i:=1 to n do write(n:3);writeln;writeln;p4(n-1);p4(n-1);for i:=1 to n do write(n:3);for i:=1 to n do write(n:3);writeln;writeln;end;end;end;end;P4(3)P4(3)1616.试用递归的方法完成下列问题(1).求n个自然数的最大公约数与最小公倍数 （利用辗转相除法）1717试用递归的方法完成下列问题(3)楼梯有n阶台阶，上楼可以一步上1阶，也可以一步上2阶，编一程序计算共有多少种不同的走法。 1818
