§7.5 递归调用
一个函数、过程或其它数据结构，如果在定义或说明的内部又直接或间接地出现定义本身的引用，则称为递归。递归调用即过程或函数自身调用自身。
递归形式一般有两种——直接递归和间接递归，而栈是实现递归的重要手段。 (一)、直接递归——子程序自己调用自己 1 n=1
【例2】 fac (n) = n! = n×fac (n-1) n>1
按上述递归定义形式写出fac(n) 函数如下： function fac(n:integer):integer; begin
if n=1 then fac:=1
else fac:=n*fac(n-1);
end;
它的执行流程如下：
fac (4) fac (3) fac (2) fac (1)
fac (4)
24
4×fac (3) 3×fac (2) 2×fac (1) fac (1) = 1
一般来说，递归子程序在调用本身前应有条件语句控制何时进行递归，何时递归结束。这个条件语句就是递归边界。例如，fac函数体中的“ if n=1 then fac:=1 ”。 · 递归调用的常用到模式：
procedure digui (参数表); 局部说明;
begin
if 边界条件 then 边界值赋值并返回 else begin 处理语句
digui(……); {递归调用} 处理语句 end; end;
· 递归调用的参数与堆栈：
① 值参数 ——在进行递归调用时，先将本层的值参保存在系统的堆栈空间中，再进入
下一层；从下一层返回时，先从堆栈中恢复本层值参的值，再往下执行。即返回后的值应是恢复后的值，也就是在进行递归调用前的值。
值参数仅仅将数据传给下一层，下一层的值参并不返回影响上层的值参。 ② 变量参数——变量参数不仅将数据传给下一层，而且会将下一层的变参的值带回到上
层。
由于递归调用须在内存中开辟堆栈区，专用于保存递归调用前的数据及地址。Pascal对堆栈区大小的默认设置为16K（16*1024byte）。若堆栈区太小，往往会发生堆栈溢出的情况，所以有时需调整堆栈区的大小。设置方法如下：
a. 选择菜单栏 Option-Compiler-Memory sizes
Stack size : 堆栈段大小，最大可设置为65520；
Low heap limit : 可接受到最小堆空间，默认为0，一般不需改动此项；
High heap limit: 指定最大堆空间，必须大于等于最小堆空间，默认为655360； b. 通过编译命令，位于程序第一行，即program之前 {$M 堆栈区大小，堆的最小值，堆的最大值} 如： {$M 65520,0,655360} (二)、间接递归——子程序A调用子程序B，子程序B又调用子程序A
子程序A和B组合起来有两种结构形式： 1．B是A的局部对象
例： procedure A;
procedure B; begin
A的子过程B… 的过程说明 A; {在B中调用A} …
end
begin
…
B; {在A中调用B}
…
end;
2．A和B是两个地位相同的子程序
例： procedure B (形式参数表): forward; {B的完整说明在后}
procedurde A; begin
…
B (实参表); {在A中调用B} end;
procedure B; {B的首部缩写，形式参数表不再列出} begin
…
A; {在B中调用A} … end;
练 习 七
1． 求给定的五个数中的最大值（用过程/函数编制求三个数的最大值，二次调用此过程/函
数）。 2． 哥德巴赫猜想之一是任何大于5的奇数都可以表示为3个素数之和，请用10个大于5的奇数验证这一论断。奇数用随机函数产生，把验证编写为过程，打印出每个数和组成该数的三个素数。 3． 编程计算组合数Cm ，将其中求 i! 编写成函数。
nCm ＝
nm!
n!?m?n?!4． 指出下列程序中的全程变量、局部变量、变量参数、数值参数，写出程序运行后的输出结
果。
Program pf; Var
a , b , c : integer;
procedure change (var x : integer; y : integer); var m,n : integer; begin
m := x * y; x := x + 1; y := y + 10; n := x + y;
writeln (‘ x= ’ , x , ’ y= ’ , y , ‘ m=’ , m , ’ n=’,
n );
end; Begin
a := 3; b := 3;
change ( a , b ); change ( a , b ); change ( a , b ); End. 5． 定义一函数 digit(n,k) ,它回送整数n的从右边开始数第k个数字的值。
例如： digit(15327,2)=5 digit(289,5)=0
6． 定义一函数 check(n,d) ,它回送一个布尔值。如果数字d在整数n的某位中出现，则回
送true，否则回送false。 例如： check(3256,2)=true check(1725,3)=false
7． 用随机函数产生数据，设计两个二位整数的加、减、乘算式各1题（减法算式应保证被减
数大于减数）。让学生回答，由计算机给出正确与否的判断，并最后给出总分。得分按如下计算：算对加、减法各得30分，算对乘法得40分，算错得0分。然后由计算机输出询问信息，学生选择回答，以决定是否继续一次新的测验。 8． 计算s。 已知：
s = 10! + 7! × 8!
将n! 定义成函数。
9． 求g(2.5 , 3.4) , g(1.7 , 2.5) , g(3.8 , 2.9) 。
?f(x?y)?f(x)?f(y)已知： g(x,y)?? ??f(x?y)??f(x)?f(y)x≤y x>y
1?e?t其中 f(t)? ，将 f和g分别定义为函数，用函数嵌套调用计算。 t1?e10．
已知：
f(x,n)?n?(n?1)?(n?2)???1?x
计算 x=3.1 , n=15 及 x=8.1 , n=10 时的f值
（用递归和递推两种方法实现） 11．
已知： f(x,n)?xn?(n?1)?xx(n?2)?x??x1?x
计算 x=3.57, n=5 时的f值, （用递归和递推两种方法实现）
12. 顺序读入字符，以“？”结束，然后以和输入相反的次序输出读入的字符，用递归过程完成。
广东省汕头市金山中学高中信息技术 竞赛班第二阶段培训 第七课 过程与函数教案
