noip讲义5-递归法(小学程度)

递归

如果函数体或过程体中出现调用其自身的语句，称为递归。

递归过程的执行流程

从下图可知，递归过程的执行总是一个过程体未执行完，

就带着本次执行的结果又进入另一轮过程体的执行，……，如此反复，不断深入，直到某次过程的执行遇到终止递归的边界条件时，则不再深入，而执行本次的过程体余下的部分，然后又返回到上一次调用的过程体中，执行其余下的部分，……，如此反复，直到回到起始位置上，才最终结束整个递归过程的执行，得到相应的执行结果。写出运行结果。var

n:integer;procedurep(n:integer);

var

i:integer;beginifn>0thenbegin

p(n-1);

fori:=1tondowrite(n);

writeln;endend;beginn:=5;

p(n);end.P(5)->P(4)->P(3)->P(2)->P(1)->P(0)122333444455555递归函数或过程通常带有一些局部变量(如本例中的n)，只有当整个函数体或过程体执行完毕时，这些局部变量才失去意义。每递归调用一次，就必须生成一组‘新’的局部变量，虽然这些新的局部变量与原来的局部变量分别具有相同的名字，但其分配的存储空间不同，其值也完全无关。递归在计算机中的实现

计算机执行递归算法时，是通过栈来实现的。在递归过程（或函数）开始运行时，系统首先为递归建立一个栈，在每次执行递归调用语句之前，自动把本算法中所使用的值参和局部变量的当前值以及调用后的返回地址压栈（称为“保存现场”，以便需要时“恢复现场”返回到某一状态），在每次递归调用结束后，又自动把栈顶元素的值分别赋给相应的值参和局部变量（出栈），以便使它们恢复到调用前的值，接着无条件转向由返回地址所指定的位置继续执行算法。例1

阶乘函数

阶乘函数可递归地定义为：边界条件递归方程

边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。

程序：

programp1(input，output)；

var

n：integer；s：

longint；

functionfac(a：integer)：longint；

beginifa=0thenfac:=1elsefac:=a*fac(a-1)；

end；

begin

readln(n)；

s:=fac(n)；

writeln(n，‘!=’，s)end．

递归过程分析-阶乘函数

阶乘函数可递归地定义为：边界条件递归方程例2:

用递归方法求两个数x和y的最大公约数。(x>0，y>0)

解1求两个数的最大公约数可以用辗转相除法，即求m与n的最大公约数等价于求（xmody）的值与y的最大公约数，此时的y可以当作新的x，而（xmody）的值当作新的y，所以原问题的求解又变成求新的m与n的最大公约数问题，继续下去，直至(xmody)为0，最大公约数就是最终存放在y中的值。递归公式：functiongcd(x,y：longint)：longint；

varr：integer；beginr:=mmodn；

ifr=0thengcd:=nelsegcd:=gcd(n,r)；｛递归调用｝

end；varr：integer；beginr:=xmody；

ifr=0thengcd:=yelsegcd:=gcd(y,r)；｛递归调用｝

end；思考：0，1，1，2，3，5，8，13，21，34，55……从第三项起，每一项都是紧挨着的前两项的和。写出计算斐波那切数列的任意一个数据项递归函数形式。

functionfic(m：integer)：longint；

beginifm=1thenfic:=0elseifm=2thenfic:=1elsefic:=fic(m-1)+fic(m-2）

｛递归调用｝

end；递归过程当一个问题可以不断的通过一种有规律的增加或递减转化为一个新问题，而解决新问题的方法和原问题相同时，可以考虑过程的递归调用，注意这种“不断的增加或递减”是有尽头的。programp4(input，output)；procedurerever；

varc：char；

beginread(c)；

ifc<>'!'thenrever;write(c)；

end；begin{主程序}

rever；end．运行：输入hey!输出!yeh。程序中，c是过程rever的局部变量。每一次递归调用，都要为局部变量重新分配单元，因此各层的变量c实际上是不同的量，它们分别用于保存执行本层调用时的输入值。

例3：输入一串以‘!’结束的字符，按逆序输出。elseProcedrue

begin

输出n的最右边的一个数字；

if还有数字then将余下的“数字倒序”

end输入一个非负数，输出这个数的倒序数。elseProcedruereverse(n:integer);

var

nr,nl:integer;beginnr:=nmod10;write(nr);

nl:=ndiv10;ifnl<>0thenreverse(nl)end;递归过程分析—数字倒序例4:

用递归算法把任一给定的十进制正整数（<=32000）转换成八进制数输出。分析：利用短除法不断除以8取余数这个重复过程，将原数据不断缩小，形成递归关系，当数据规模缩小至0时，递归结束。proceduretran(n:longint);{递归过程}

var

k:longint;begink:=nmod8;{取除以8以后的余数}n:=ndiv8;{取除以8以后的商}ifn<>0thentran(n);{直到商为0，结束递归过程}write(k:1)end;在调用过程或函数之前，系统需完成三件事：⑴为被调用过程的局部变量分配存储区；⑵将所有的实在参数、返回地址等信息传递给被调用过程保存；⑶将控制转移到被调过程的入口。从被调用过程返回调用过程之前，系统也应完成三件工作：⑴保存被调过程的计算结果；⑵释放被调过程的数据区；⑶依照被调过程保存的返回地址将控制转移到调用过程。例5、由m个A，n个B组成若干个排列。从某个排列的位置1开始数，数到任意位置时都能保证A的个数不少于B的个数，则称该排列为合理排列。例如：当m=2，n=2时排列有AABB(合理)ABAB(合理)ABBA(不合理)BBAA(不合理)合理排列数有2种输入：只有一行两个整数m,n（1≤n≤m≤12）（用空格分隔）输出：一个整数（所有的合理排列数）【样例】输入输出325分析：模拟排队的情况，从第1个人开始，第1人只能是A，第2个可以是A也可以是B，再其后的人要保证任意位置时都能保证A的个数不少于B的个数，递归求有多少个排列。Var

m,n,t:LongInt;Procedurepd(i,j:LongInt);BeginIf(i=m)And(j=nThent:=t+1{已生成一种排列}ElseBeginIfi<mThenpd(i+1,j);{增加1个A}If(j<n)And(j<i)Thenpd(i,j+1);End;{增加1个B}End;Begint:=0;Read(m,n);pd(1,0);Writeln(t);End.(i=m)And(j=n)pd(i+1,j);(j<n)And(j<i)例7、汉诺塔（towerofHanoi）问题。有n个大小不等的中空圆盘，按照从小到大的顺序迭套在立柱A上，另有两根立柱B和C。现要求把全部圆盘从A柱（源柱）移到C柱（目标柱），移动过程中可借助B柱（中间柱）。移动时有如下的要求：①一次只移动一个盘；②不允许把大盘放在小盘上边；③可使用任意一根立柱暂存圆盘。先以三个盘的移动为例，看一下移动过程。

分析：首先将A柱上方的n-1个盘子从A柱移到B柱，此过程中C柱为中间柱；接着将A柱剩下的一个盘子移到C柱；最后再将B柱上的n-1个盘子移到C柱，此过程中A柱为中间柱，这就变成了移动n-1个盘子的问题了。定义过程hanoi，实现这一递归算法：若n=1，则A→C

若n>=2，则hanoi(n-1，A，C，B)

A→C

hanoi(n-1，B，A，C)运行结果：EnterthenumberofdisksinHanoitower：3A→CA→BC→BA→CB→AB→CA→Cvarn：integer；procedurehanoi(n:integer;x,y,z：char)；begin

ifn=1thenwriteln(x,‘->’,n,‘->’,z)

elsebegin

hanoi(n-1,x,z,y)；

writeln(x,‘->’,n,‘->’,z)；

hanoi(n-1,y,x,z)endend；begin

{主程序）

readln(n)；

hanoi(n,‘A’,‘B’,‘C’)end．解2求两个数的最大公约数可以用辗转相减法

f(x,y)=f(y,x-y)

避免了大整数的取模运算。但迭代次数太多。f(48,28)=f(28,20)=f(20,8)=f(12,8)=f(8,4)=f(4,0)分析：

1.如果y=k*y1，x=k*x1，有f(y,x)=k*f(y1,x1)。2.如果x=p*x1，假设p是素数，并且y不能被p整除，那么f(x,y)=f(p*x1,y)=f(x1,y)。例8再探1:

用递归方法求两个数x和y的最大公约数。(x>0，y>0)

functionfic(m：integer)：longint；

beginifm=1thenfic:=0elseifm=2thenfic:=1elsefic:=fic(m-1)+fic(m-2）

｛递归调用｝

end；例9

再探Fibonacci数列

优化？递归要素：完成递归必须考虑的因素有两个。

（1）边界条件。也就是所描述问题的最简单情况，它本身不再使用递归的定义。如阶乘，当n=0时，f(n)=1，不使用f(n-1)来定义。（2）递归关系。使问题向边界条件转化的规则。递归定义必须能使问题的规模越来越简单。递归的优点：长处是，它能使一个蕴含递归关系且结构复杂的程序简介精炼，增加可读性。特别是在难于找到从边界到解的全过程的情况下，如果把问题推进一步,其结果仍维持原问题的关系，则采用递归算法编程比较合适。递归的缺点：递归算法的效率往往很低，费时和费内存空间。FreePascal理论上可以使用4GB（2^32byte）的内存，因此实际上几乎可以使用系统中的所有剩余内存（但有时赛题中有内存限制），这是因为FreePascal使用的是32位的编译器。但大量数据的处理过程将会耗时,有时将出现超时。解决方法：在递归算法中消除递归调用，使其转化为非递归算法。1、采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。2、用递推来实现递归函数。3、通过变换能将一些递归转化为尾递归，从而迭代求出结果。后两种方法在时空复杂度上均有较大改善，但其适用范围有限。如何设计递归算法

一个问题要用递归方法来解决必须符合两个条件：1、可以把一个问题转化成一个新的问题，而新问题的解法和原问题的解法完全相同，只是处理对象的规模不同。2、必顺要有一个明确的递归结束条件。例1、翻硬币(03年初赛题)

题目描述：一摞硬币共有m枚，每一枚都是正面朝上。取下最上面的一枚硬币，将它翻面后放回原处。然后取下最上面的2枚硬币，将他们一起翻面后再放回原处。再取3枚，取4枚……直至m枚。然后再从这摞硬币最上面的一枚开始，重复刚才的做法。这样一直做下去，直到这摞硬币中的每一枚又都是正面朝上为止。输入：仅有的一个数字是这摞硬币的枚数m，0<m<50。输出：为了使这摞硬币中的每一枚又都是正面朝上所必需翻的次数。输入样例：

30输出样例：

899constmax=100;var

a,b:array[1..max]ofboolean;

m,n:integer;procedureprint;

var

i:integer;

p:boolean;begin

（）；

p:=true;fori:=1tomdoifa[i]thenp:=false;ifpthenbegin

writeln('total=',n);

（）;end;end;procedureturn(k:integer);

var

i:integer;beginifk>mthen（）;b:=a;fori:=1tokdo

b[i]:=not(

);a:=b;print;

（）；

end;begin

readln(m);

fillchar(a,sizeof(a),false);n:=0;｛翻面次数｝

turn(1);｛翻一个硬币｝end.k:=1halta[k+1-i]turn(k+1)inc(n)例2、求全排列(06年初赛题)

下面程序的功能是利用递归方法生成从1到n(n<10)的n个数的全部可能的排列（不一定按升序输出）。例如，输入3，则应该输出（每行输出5个排列）：123132213231321312

var

i,n,k:integer;a:array[1..10]ofinteger;

count:longint;procedureperm(k:integer);

var

j,p,t:integer;begin

if()thenbegin();forp:=1tokdowrite(a[p]:1);write('');if()then

writeln;exit;end;

forj:=ktondobegint:=a[k];

a[k]:=a[j];

a[j]:=t;perm(k+1);t:=a[k];()

endend;begin

writeln('Entryn:');

read(n);count:=0;fori:=1tondoa[i]:=i;()end.perm(1)K=ninc(count)countmod5=0a[k]:=a[j];a[j]:=t;123123123132123132213213213231231321321321312312例3、2的幂次方表示(98年复赛)

任何一个正整数都可以用2的幂次方表示。例如：137=27+23+20同时约定次方用括号来表示，即ab可表示为a(b)。由此可知，137可表示为：2(7)+2(3)+2(0)

进一步：7=22+2+20(21用2表示)3=2+20所以最后137可表示为：2(2(2)+2+2(0))+2(2+2(0))+2(0)又如：1315=210+28+25+2+20所以1315最后可表示为：2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)输入：一个正整数(n<=20000)输出：符合约定的n的0,2表示(在表示中不能有空格)var

n:longint;proceduretry(n:longint);

vara:array[1..1000]ofinteger;

k,p,i,t:longint;beginfillchar(a,sizeof(a),0);

k:=n;p:=0;t:=0;while()dobegin

inc(p);

a[p]:=kmod2;if(a[p]<>0)and(t=0)thent:=p;

{t记录二进制数中从最低位开始第一个'1'的位置}k:=kdiv2;end;fori:=pdowntot+1doifa[i]=1thenif()thenwrite('2+')elsebegin

write('2(');();write(')+');end;{情况一}if()thenwrite('2(0)')elsebeginift=2thenwrite('2')elsebeginwrite('2(');();write(')');end;end;{情况二}end;begin

readln(n);

try(n);end.由于最后一项后面没有加号，其它项之后有加号，因此程序中进行了区别对待．k>0i=2try(i-1)t=1try(t-1)给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度≤8）。[样例]输入：BADCBDCA输出：ABCD

分析:

通过对比二叉树的中序与后序排列，我们可以找出根节点及左右子树。同样的，也可以通过对比左子树的中序与后序排列，找出左子树的根节点……可见，该问题能够被递归描述。当找到最后一个根节点时，递归无法再进行下去，这就是递归结束的边界条件。