课件pascal语言讲递归.pptx

第十二讲：递归;递归的概念：

一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数).

满足某个条件后递归终止。;例1：计算n!

可用公式如下:

f(1)=1当n=1时??

f(n)=n*f(n-1)当n1时;var

n:integer;

functionf(i:integer):integer;

begin

ifi=1thenf:=1;

f:=i*f(i-1);

end;

begin

readln(n);

writeln(f(n));

end.;一个含有n个台阶的楼梯，一个人上楼时可以一步上1个台阶，也可以一步上2个台阶，还可以一步上3个台阶。编一个程序，计算共有多少种不同的走法。(n=36);varn:integer;

functionf(n:integer):integer;

begin

ifn=1thenf:=1

elseifn=2thenf:=2

elseifn=3thenf:=4

elsef:=f(n-3)+f(n-2)+f(n-1);

end;

begin

read(n);

writeln(f(n));

end.;var

n:longint;

functionf(n:longint):longint;

begin

ifn=1thenexit(1);

ifn=2thenexit(2);

ifn=3thenexit(4);

f:=f(n-1)+f(n-2)+f(n-3);

end;

begin

readln(n);

writeln(f(n));

end.;递归的关键：

1.确定递归公式（关系）

2.确定边界(终止)条件;1、

functionf(m:integer):integer;

varva:integer;

begin

ifm=0thenf:=3

elsef:=f(m-1)+5;

end.

Begin

writeln(f(3));

End.;2、

var

n:longint;

procedurechange(n:longint);

begin

ifn0then

begin

change(ndiv2);

write(nmod2);

end;

end;

begin

readln(n);

change(n);

end.;3、

varn:integer;

proceduref(n:integer);

begin

ifn0then

begin

f(n-1);

write(n);

f(n-1);

end;

end;

begin

f(3);

end.;4、已知ack(m,n)函数的计算公式如下：;varm,n:integer;

functionack(m,n:integer):integer;

begin

ifm=0thenack:=n+1

elseifn=0thenack:=ack(m-1,1)

elseack:=ack(m-1,ack(m,n-1));

end;

begin

read(m,n);

writeln(ack(m,n));

end.;递归的简单应用;问题的提出：

Hanoi塔由n个大小不同的圆盘和3根木柱1,2,3组成。开始时，这n个圆盘由大到小依次套在1柱上，如图所示。

现在要求用最少的移动次数把1柱上n个圆盘按下述规则移到3柱上：

(1)一次只能??一个圆盘；

(2)圆盘只能在3个柱上存放；

(3)在移动过程中，不允许大盘压小盘。

请编程描述移动的过程。。;1:1--3;

第一步：先借助3柱把1柱上面的n-1个盘子移动到2柱上。

第二步：然后再把1柱最下面的一个盘子移动到3柱上。

第三步：再借助1柱把2柱上的n-1个盘子移动到3上。;procedure