过程与函数
我们学习了程序设计中的三种基本控制结构（顺序、分支、循环）。用它们可以组成任何程序。
通常，在程序设计中，我们会发现一些程序段在程序的不同地方反复出现，此时可以将这些程序段作为相对独立的整体，用一个标识符给它起一个名字，凡是程序中出现该程序段的地方，只要简单地写上其标识符即可。这样的程序段，我们称之为子程序。
子程序的使用不仅缩短了程序，节省了内存空间及减少了程序的编译时间，而且有利于结构化程序设计。因为一个复杂的问题总可将其分解成若干个子问题来解决，如果子问题依然很复杂，还可以将它继续分解，直到每个子问题都是一个具有独立任务的模块。这样编制的程序结构清晰，逻辑关系明确，无论是编写、阅读、调试还是修改，都会带来极大的好处。
在一个程序中可以只有主程序而没有子程序(本章以前都是如此)，但不能没有主程序，也就是说不能单独执行子程序。pascal中子程序有两种形式：函数和过程。Pascal本身提供一些标准函数（如abs(x)、sqr(x)等和标准过程（如readln、write等）。
函数
如果一个子程序执行后能够返回其结果值，那么它就可以用于表达式中，称这种子程序称为函数。
（一）函数的说明
在pascal中，函数也遵循先说明后使用的规则，在程序中，函数的说明放在调用该函数的程序（主程序或其它子程序）的说明部分。函数的结构主程序的结构很相似。
函数定义的一般格式:
function <函数名> (<形式参数表>):<类型>; {函数首部}
说明:
① 函数由首部与函数体两部分组成。
② 函数首部以关键字function开头。
③ 函数名是用户自定义的标识符。
④ 函数的类型也就是函数值的类型，所求得的函数值通过函数名传回调用它的程序。可见，函数的作用一般是为了求得一个值。
⑤ 形式参数简称形参，形参即函数的自变量。自变量的初值来源于函数调用。在函数中，形参一般格式如下：
变量名表1：类型标识符1；变量名表2：类型标识符2；…;变量名表n：类型标识符n
可见形参表相当于变量说明，对函数自变量进行说明，但应特别注意：此处只能使用类型标识符，而不能直接使用类型。
⑥ 当缺省形参表（当然要同时省去一对括号）时，称为无参函数。
⑦ 函数体与程序体基本相似，由说明部分和执行部分组成。
⑧ 函数体中的说明部分用来对本函数使用的标号、常量、类型、变量、子程序加以说明，这些量只在本函数内有效。
⑨ 函数体的执行部分由begin开头，end结束
，中间有若干用分号隔开的语句，只是end后应跟分号,不能像程序那样用句号"."。
⑩ 在函数体的执行部分，至少应该给函数名赋一次值，以使在函数执行结束后把函数值带回调用程序。
例1、计算n!的函数
function fac(n:integer):integer;
var k,m:integer;
begin
m:=1;
for k:=2 to n do m:=m*k;
fac:=m; {将计算结果值赋给函数，返回调用处 }
end;
函数值将通过函数名传送回调用的程序。因此，函数体中每次求值至少要有一条语句对函数名赋值。如函数fac:=m，计算求得一个值，返回时就把这个值带回调用的地方。
2、函数的调用
自定义函数只限于在定义它的程序中使用。函数调用形式为：
函数名( 实在参数表 );
函数调用必须出现在表达式中，且调用的自定义函数在之前已定义过；
实参表是若干由逗号分隔的参数。在调用函数时，实参应有确定的值，实参将值赋给形参，因此，实参的个数、类型应与形参一一对应。
函数调用的步骤是先在调用程序中计算实参的值，传送给对应的形参，然后执行函数体，最后将函数值返回调用程序处。 如函数定义后未被调用，则该函数将不会被执行。
例2：计算|X|的函数
function zhoufei(x:real):real;
var z:integer;
begin
if x>=0 then z:=x
else z:=-x
zhoufei:=z;
end;
例3、编程，对6到100的偶数验证哥德巴赫猜想：任一个大于等于6的偶数总可以分解为两个素数之和。输出每个数是哪两个素数之和。
var a,i,j:integer;
function fect(m:integer):boolean;
var k,s:integer;
begin
s:=trunc(sqrt(m)); k=2;
while (m mod k<>0)and (k<=s) do k:=k+1;
if k>s then fect:=true else fect:=false;
end;
begin
for i:=6 to 100 do
for j:=3 to trunc(i/2) do
if fect(j) and fect(i-j) then writeln(i,'=',j,'+',i-j)
end.
例4、求正整数a和b之间的完全数（a
它们都能写成连续自然数之和：
6=1+2+3,
28=1+2+3+4+5+6+7,
496=1+2+3+4+……+31,
8128=1+2+3+4+……+127；
2. 它们的全部因数的倒数之和都是2。
1/1+1/2+1/3+1/6=2
1/1+1/2+1/4+1/7+1/(14)+1/(28)=2
1/1+1/2+1/4+1/8+1/(16)+1/(31)+1/(62)+1/(124)+1/(248)+1/(496)=2
var a,b,i,j,n: integer;
c:array[1..20] of integer;
function fac(x:integer):boolean;
var k,sum:integer;
begin
sum:=1; n:=0;
for k:=2 to x div 2 do
if x mod k=0 then begin n:=n+1
; c[n]:=k; sum:=sum+k end;
if x=sum then fac:=true else fac:=false;
end; { 将计算结果值true 或false赋给函数fac，返回调用处 }
begin { 主程序 }
write('input a,b:');
repeat readln(a,b) until (a>0) and (b>0) and (a
if fac(i) then { 调用函数fac,如返回值为true,输出完全数 }
begin
write(i,'=1');
for j:=1 to n do write('+',c[j]);
writeln
end;
end.
输入：2 1000
输出：6=1+2+3
28=1+2+4+7+14
496=1+2+4+8+16+31+62+124+248
过程
给某个语句序列组成的子程序赋于一个标识符。程序中凡是需要出现这个语句序列的地方，可以简单的写上该子程序的标识符。这样完成一个操作的子程序称为过程。
（一）过程的说明
过程说明的一般格式为：
procedure <过程名> (<形式参数表>); {过程首部}
说明:
① 过程首部以关键字procedure开头。
② 过程名是用户自定义的标识符，只用来标识一个过程，不能代表任何数据，因此不能说明"过程的类型"。
③ 形参表缺省（当然要同时省去一对括号）时，称为无参过程。
④ 形参表的一般格式形式如下：
[var] 变量名表：类型；…；[var] 变量名表：类型。
其中带var的称为变量形参，不带var的称为值形参。在函数中，形参一般都是值形参，很少用变量形参（但可以使用）。例如，下列形参表中：
(x,y:real;n:integer;var w:real;var k:integer;b:real)
x、y、n、b为值形参,而w、k为变量形参。
调用过程时，通过值形参给过程提供原始数据，通过变量形参将值带回调用程序。因此，可以说，值形参是过程的输入参数，变量形参是过程的输出参数。有关变参，这在后面内容具体叙述。
⑤ 过程体与程序、函数体类似。与函数体不同的是：函数体的执行部分至少有一个语句给函数名赋值，而过程体的执行部分不能给过程名赋值，因为过程名不能代表任何数据。
⑥ 过程体的说明部分可以定义只在本过程有效的标号、常量、类型、变量、子程序等。
例1：定义过程求n!。
Var t:longint ; a:integer ;
procedure jc(n:integer);
var k:integer;
begin { 变量t在主程序中说明 }
t:=1;
for k:=2 to n do t:=t*k; { 最后由t将n!值返回调用程序 }
end;
begin
readln(a) ;
jc(a+2) ;
writeln(t) ;
end.
例2：输出两个数中最大值的过程
procedure largest(a,b:integer ; var max : integer);
begin
if a>b then max:=a
else max:=b;
end.
Var a1,a2,m:integer;
begin
Readln(a1,a2);
Largest(a1,a2,m);
Writeln(m);
End.
例3：比较三个数，输出最大数
方法一：
procedure largest(a,b,c:integer; var m:integer)
begin
if a>b then m:=a else m:=b;
if m
var x,y,z,max:integer;
begin
readln(x,y,z);
largest(x,y,z,max);
writeln(max);
end.
方法二：
procedure largest(a,b,c:integer; var m:integer);
var t:integer;
procedure larger(n,m:integer; var r:integer);
begin
if n>m then r:=n else r:=m;
end;
begin
larger(a,b,t);
larger(t,c,m);
end;
var x,y,z,max:integer;
begin
readln(x,y,z);
largest(x,y,z,max);
writeln(max);
end.
除函数首部和过程首部的句法略有差别外，函数体和过程体完全相同。函数返回一个函数值，过程则能完成一系列各种操作。函数的调用方式出现在表达式中，而过程调用是一句独立的语句。与函数不同，不能给过程名赋值。
过程与函数中的参数
一、参数的调用
函数调用或过程调用的执行步骤分为以下几步：
实参和形参结合 → 执行函数或过程体 → 返回调用处继续执行
函数或过程说明的形参表对函数或过程体直接引用的变量进行说明，详细指明这些参数的类别、数据类型要求和参数的个数。函数或过程被调用时必须为它的每个形参提供一个实参，按参数的位置顺序一一对应，每个实参必须满足对应形参的要求。
形参可分为两类：值形参，变量形参。
1、值形参
值参的一般格式如§7.1.1所示。应该强调的是：
①形参表中只能使用类型标识符，而不能使用类型。
②值形参和对应的实参必须一一对应，包括个数和类型。
③实参和值形参之间数据传递是单向的，只能由实参传送给形参，相当赋值运算。
④一个特殊情况是，当值形参是实型变量名时，对应的实参可以是整型表达式。
⑤值形参作为子程序的局部量，当控制返回程序后，值形参的存储单元释放。
2、变量形参
变量形参的一般格式如§7.2.1所示，必须在形参前加关键字var。
应该注意的是：
①与变量形参对应的实参只能是变量名，而不能是表达式。
②与变量形参对应的实参可以根据需要决定是否事先有值。
③变量形参与对应的实参的类型必须完全相同。
④对变量形参，运行时不另外开辟存储单元，而是与对应的实参使用相同的存储单元。也就是说，调用子程序时，是将实参的地址传送给对应的变量形参。
⑤当控制返回到调用程序后，变量形参的存储单元不释放，但变量形参本身无定义，即不得再使用。
⑥选用形式参时，到底是使用值形参还是变量形参，应慎重考虑。值形参需要另开辟存储空间，而变量形参会带来一些副作用。一般在函数中使用值形参，而在过程中才使用变量形
参，但也有例外。
例、写出下列两个程序的运行结果。
program ex1; program ex2;
var a,b:integer; var a,b:integer;
procedure swap(x,y:integer); procedure swap(Var x,y:integer) ;
var t:integer; var t:integer;
begin begin
t:=x;x:=y;y:=t; t:=x;x:=y;y:=t;
end; end;
begin begin
a:=1;b:=2; a:=1;b:=2;
writeln(a:3,b:3); writeln(a:3,b:3);
swap(a,b); swap(a,b);
writeln(a:3,b:3); writeln(a:3,b:3);
end. end.
分析：这两个程序唯一的区别是ex1中将x,y作为值形参，而 ex2中将x,y作为变量形参，因此在ex2中对x,y的修改实际上是对调用该过程时与它们对应的变量a,b的修改，故最后，a,b的值为2，1。而ex1中调用swap过程时，只是将a,b的值传递给x,y，之后在过程中的操作与a,b无关。
答：ex1的运行结果为: ex2的运行结果为:
1 2 1 2
1 2 2 1
例1：定义过程swap，完成变量 a和b的交换。
程序一
var a,b:integer;
procedure swap;
var t:integer; { 通过全程变量将过程中的值传回主程序 }
begin t:=a; a:=b; b:= t end;
begin
a:=10; b:=20; writeln('a=',a, ' b=',b);
swap; writeln('a=',a, ' b=',b);
end.
程序二
var a,b:integer;
procedure swap(var m,n:integer); { 通过变量参数将过程中的值传回主程序 }
var t:integer;
begin t:=m; m:=n; n:=t end;
begin
a:=10; b:=20; writeln('a=',a, ' b=',b);
swap(a,b); writeln('a=',a, ' b=',b);
end.
程序三
var a,b:integer;
procedure swap(m,n:integer); { 本程序不能完成两个变量值的交换，为什么？ }
var t:integer;
begin t:=m; m:=n; n:= t end;
begin
a:=10; b:=20; writeln('a=',a, ' b=',b);
swap(a,b); writeln('a=',a, ' b=',b);
end.
m,n为值形数，它类似局部变量，仅为过程和函数提供初值而不影响调用时实参的值。
例2：设计一个过程，将数组中的元素从大到小排列。
type atype= array[1..10] of integer;
var a: atype; { a 为数组类型 }
n:integr;
procedure sort(var b: atype); { 变量形参b为数组参数 }
var i,j,k:integer;
begin
for i:=1 to 9 do
for j:=i+1 to 10 do
if b([i]
begin { 主程序 }
for i:=1 to 10 do read(a[i]);
sort(a); { 过程调用，实参a为数组类型 }
for i:=1 to 10 do write(a[i], ' ')
end.
过程中对变参b的操作就是对实参a的操作。当形参为数组类型时，必须用类型名进行定义。不能写成: procedure sort(var b:array[1..10] of integer);
二、变量及其作用域
1.全程变量的作用域
全程变量是指在程序开头的说明部分定义和说明的量。它的作用域分为两种情况：
(1)在全程变量和局部变量不同名时，其作用域是整个程序。
(2)在全程变量和局部变量同名时，全程变量的作用域不包含同名局部变量的作用域。
2.局部变量的作用域
凡是在子程序内部使用的变量，必须在子程序中加入说明。这种在子程序内部说明的变量称为局部变量。局部变量的作用域是其所在的子程序。形式参数也只能在子程序中有效。因此也属于局部变量。局部变量的作用域分为两种情况：
(1)当外层过程的局部变量名和嵌套过程中的局部变量不同名时，外层过程的局部变量作用域包含嵌套过程。
(2)当外层过程的局部变量名和嵌套过程内的局部变量名同名时，外层局部变量名的作用域不包含此过程。
引入局部变量可以节省内存空间,且便于结构化程序设计。在某些程序中，为了使变量间不互相干扰，一般采用局部变量。如变量间需某种联系时，则可选择全程变量或形参。
例4 写出下列程序的运行结果:
program ex7_4;
var x,y:integer;
procedure a;
var x:integer;
begin
x:=2;
writeln('#',x,'#');
writeln('#',y,'#');
end;{of a}
begin{main program}
x:=1;y:=2;
writeln('*',x,'*'，y);
a;
writeln('***',x,'***',y);
end.
分析：程序中x,y是全局变量,但在过程a中也有变量x，故全程变量x的作用域为除过程a外的任何地方。而y的作用域包含了子程序a，即整个程序。
答：运行结果如下:
*1*2
#2#
#2#
***1***2
评注：变量作用域内对变量的操作都是对同一存储单元中的量进行的。
四、程序的嵌套和超前引用
1、 程序的嵌套
一个过程或函数调用另一个过程或函数，称为过程与函数的嵌套。嵌套是一层套一层的程序结构，从外向内逐层相包。注意：
①内、外层不能相互交叉，内层必须完全嵌套在外层之中；
②一般情况下，过程或函数内部需要使用的变量应在内部进行定义。
外层不能访问内层所定义的变量。
2、 超前引用
有时程序在并列的函数或过程需要相互调用，或前面定义过的过程或函数需调用后面定义函数或过程。这就违反了标识符必须先定义后使用的原则。解决这个问题的方法是适当处理后，超前引用。
例6、设有下列函数和过程：
procedure a(m,n:integer);
{ a的过程体 }
procedure b(x:integer);
{ b的过程体 }
function (s:integer):integer;
{ c的函数体 }
如果a调用b和c，而b和c 又调用a，写出这些函数和过程的说明次序。
解：
procedure b(x:integer); forward; { 过程b的首部提前 }
function c(s:integer):integer; forward; { 函数c的首部提前 }
procedure a(m,n:integer); { a的过程体 }
procedure b; { 过程b被提前引用后，此处去掉形参表 }
{ b的过程体 }
function c; { 函数c被提前引用后，此处去掉形参表和函数类型 }
{ c的函数体 }
五、递归调用
如果一个过程或函数又直接或间接调用自身，称为递归。
使用递归求解问题，一般可将一个比较大的问题层层转化为与原问题类似的、规模较小的问题进行求解，最终达到对原问题的解决。
递归的关键在于找出递归方程式和递归终止条件。
例1、 植树节那天，有五位参加了植树活动，他们完成植树的棵数都不相同。问第一位同学植了多少棵时，他指着旁边的第二位同学说比他多植了两棵；追问第二位同学，他又说比第三位同学多植了两棵；…如此，都说比另一位同学多植两棵。最后问到第五位同学时，他说自己植了10棵。到底第一位同学植了多少棵树？
递归算法是把处理问题的方法定义成与原问题处理方法相同的过程，在处理问题的过程中又调用自身定义的函数或过程。
解：把原问题求第一位同学在植树棵数a1，转化为a1=a2+2;即求a2；而求a2又转化为a2=a3+2; a3=a4+2; a4=a5+2;逐层转化为求a2,a3,a4,a5且都采用与求a1相同的方法；最后的a5为已知,则用a5=10返回到上一层并代入计算出a4；又用a4的值代入上一层去求a3;...,如此,直到求出a1。
因此：
其中求a x + 1 又采用求a x 的方法。所以:
① 定义一个处理问题的过程Num(x)：如果X < 5就递归调用过程Num(x+1);
② 当递归调用到达一定条件(X=5)，就直接执行a :=10，再执行后继语句，遇End返回到调用本过程的地方，将带回的计算结果(值)参与此处的后继语句进行运算（a:=a+2）;
③ 最后返回到开头的原问题，此时所得到的运算结果就是原问题Num(1)的答案。
Pascal程序：
Program Exam1_1;
Var a: byte;
Procedure Num(x: integer);{过程Num(x)求x的棵数｝
begin
if x=5 then a:=10
else begi
n
Num(x+1); ｛递归调用过程Num(x+1)｝
a:=a+2 {求(x+1)的棵数｝
end
end;
begin
Num(1); ｛主程序调用Num(1)求第1个人的棵数｝
writeln(’The Num is ’, a);
readln
end.
程序中的递归过程图解如下：
参照图示，递归方法说明如下：
① 调用原问题的处理过程时，调用程序应给出具体的过程形参值（数据）;
② 在处理子问题中，如果又调用原问题的处理过程，但形参值应是不断改变的量(表达式）;
③ 每递归调用一次自身过程，系统就打开一“层”与自身相同的程序系列;
④ 由于调用参数不断改变，将使条件满足（达到一定边界），此时就是最后一“层”，不需再调用（打开新层），而是往下执行后继语句，给出边界值，遇到本过程的END，就返回到上“层”调用此过程的地方并继续往下执行;
⑤ 整个递归过程可视为由往返双向“运动”组成，先是逐层递进，逐层打开新的“篇章”，（有可能无具体计算值）当最终递进达到边界，执行完本“层”的语句，才由最末一“层”逐次返回到上“层”，每次返回均带回新的计算值，直至回到第一次由主程序调用的地方，完成对原问题的处理。
例2、用递归算法求X n 。
解：把X n 分解成: X 0 = 1 ( n =0 )
X 1 = X * X 0 ( n =1 )
X 2 = X * X 1 ( n >1 )
X 3 = X * X 2 ( n >1 )
…… ( n >1 )
X n = X * X n-1 ( n >1 )
因此将X n 转化为：
其中求X n -1 又用求X n 的方法进行求解。
①定义过程xn(x,n: integer)求X n ;如果n >1则递归调用xn (x, n-1) 求X n—1 ;
②当递归调用到达n=0，就执行t t :=1, 然后执行本“层”的后继语句;
③遇到过程的END就结束本次的调用，返回到上一“层”调用语句的地方，并执行其后续语句tt:=tt*x;
④继续执行步骤③，从调用中逐“层”返回，最后返回到主程序，输出tt的值。
Pascal程序：
Program Exam2;
Var tt, a, b: integer;
Procedure xn(x, n: integer); ｛过程xn(x, n)求xn ｝
begin if n=0 then tt:=1
else begin
xn(x, n-1); ｛递归调用过xn(x,n-1)求x n-1｝
tt:=tt*x
end;
end;
begin
write(’input x, n:’); readln(a,b); ｛输入a, b｝
xn(a,b); ｛主程序调用过程xn(a, b)求a b｝
writeln(a, ’^’, b, ’=‘, tt);
readln
end.
递归算法，常常是把解决原问题按顺序逐次调用同一“子程序”(过程)去处理，最后一次调用得到已知数据，执行完该次调用过程的处理，将结果带回，按“先进后出”原则，依次计算返回。
如果处理问题的结果只需返回一个确定的计算值，可定义
成递归函数。
例3、用递归函数求x!
解：根据数学中的定义把求x! 定义为求x*(x-1)! ,其中求(x-1)! 仍采用求x! 的方法，需要定义一个求a！的过程或函数，逐级调用此过程或函数，即：
(x-1)!= (x-1)*(x-2)! ;
(x-2)!= (x-2)*(x-3)! ;
……
直到x=0时给出0!=1，才开始逐级返回并计算各值。
①定义递归函数：fac(a: integer): integer;
如果a=0，则fac:=1;
如果a>0，则调用函数fac:=fac(a-1)*a;
②返回主程序，打印fac(x)的结果。
Pascal程序：
Program Exam3;
Var x: integer;
function fac(a: integer): integer; ｛函数fac(a) 求a !｝
begin
if a=0 then fac:=1
else fac:=fac(a-1)*a ｛函数fac(a-1)递归求(a-1) !｝
end;
begin
write(’input x’); readln(x);
writeln(x, ’!=’, fac(x)); ｛主程序调用fac(x) 求x !｝
readln
end.
递归算法表现在处理问题的强大能力。然而，如同循环一样，递归也会带来无终止调用的可能性，因此，在设计递归过程（函数）时，必须考虑递归调用的终止问题，就是递归调用要受限于某一条件，而且要保证这个条件在一定情况下肯定能得到满足。