Pascal递归算法.doc

第七讲 递归算法 　　 【递归的定义】 　　 为了描述问题的某一状态，必须用到它的上一状态，而描述上一状态，又必须用到它的上一状态……这种用自已来定义自己的方法，称为递归定义。　　例如：定义函数f(n)为： 则当n0时，须用f(n-1)来定义f(n),用f(n-1-1)来定义f(n-1)……当n=0时，f(n)=1。 　　由上例我们可看出，递归定义有两个要素： 　　（1）递归边界条件。也就是所描述问题的最简单情况，它本身不再使用递归的定义。 　　如上例，当n=0时，f(n)=1，不使用f(n-1)来定义。 　　（2）递归定义：使问题向边界条件转化的规则。递归定义必须能使问题越来越简单。 　　如上例：f(n)由f(n-1)定义，越来越靠近f(0),也即边界条件。最简单的情况是f(0)=1。 　　 递归算法的效率往往很低, 费时和费内存空间. 但是递归也有其长处, 它能使一个蕴含递归关系且结构复杂的程序简介精炼, 增加可读性. 特别是在难于找到从边界到解的全过程的情况下, 如果把问题推进一步没其结果仍维持原问题的关系, 则采用递归算法编程比较合适. 　　 递归按其调用方式分为: 　　 1. 直接递归, 递归过程P直接自己调用自己；　　 2. 间接递归, 即P包含另一过程D, 而D又调用P。　　 递归算法适用的一般场合为: 　　 1. 数据的定义形式按递归定义. 　　 如裴波那契数列的定义: f(n)=f(n-1)+f(n-2); f(0)=1; f(1)=2. 　　 对应的递归程序为: 　　　Function fib(n : integer) : integer; 　　　Begin 　　　　　if n = 0 then fib := 1 { 递归边界 } 　　　　 　　　else if n = 1 then fib := 2 { 递归边界 }　　　　　　　　　　else fib := fib(n-2) + fib(n-1) { 递归 } 　　　End; 　　 这类递归问题可转化为递推算法, 递归边界作为递推的边界条件. 　　 2. 数据之间的关系(即数据结构)按递归定义. 如树的遍历, 图的搜索等. 　　 3. 问题解法按递归算法实现. 例如回溯法等. 　　 【举例】　　 例1：楼梯有n阶台阶，上楼可以一步上1阶，也可以一步上2阶，编一程序计算共有多少种不同的走法。 　　〖问题分析〗：　　 设n阶台阶的走法数为f(n)，显然有： 　　 　　〖参考程序〗： 　　例：求m与n的最大公约数。　　〖问题分析〗：　　 从数学上可以知道求m与n的最大公约数等价于示n与（m MOD n）的最大公约数。这时可以把n当作新的m，（m MOD n）当作新的n，问题又变成了求新的m与n的最大公约数。它又等价于求新的n与（m MOD n）的最大公约数……如此继续，直到新的n=0时，其最大公约数就是新的m。　　 例如求24与16的最大公约数，等价于求16与（24 MOD 16）的最大公约数，即求16与8的最大公约数。它又等价于求8与（16 MOD 8）的最大公约数，即求8与0的最大公约数。此时n=0，最大公约数就是8。　　 这样我们可以得出递归模型为：　　 其中Gcd(m,n)代表求m与n的最大公约数。　　〖参考程序〗： 　　 Var　　 m,n,g:integer;　　 function gcd(m,n:integer):integer;　　　 begin　　　　　 if n=0 then gcd:=m　　　　　　　　　else gcd:=gcd(n,m MOD n); 　　　 end; 　　 begin　　　　read(m,n);　　　　g:=gcd(m,n);writeln(m=,m,n=,n,gcd=,g);　　 　　end. 第 2 页 共 2 页 var n:integer; 　　 function f(x:integer):integer; 　　　 begin 　　 　　if x=1 then f:=1 else 　　 　　if x=2 then f:=2 else f:=f(x-1)+f(x-2); 　　　end; 　　begin 　　　　write(n=);read(n); 　　　　writeln(f(,n,)=,f(n)) 　　end.