第 3 章 函数和递归函数 3.1 编写函数的优点 程序设计语言中的函数的概念与通常的数学概念差别很大, 尽管它们也具有一些相似之处 因此, 初看上去可能会令人混淆, 以至于不能做出明确的比较 我们更愿意在 Java 中介绍函数的语法, 并且说明它的两个基本的优点 : 函数可以作为用于增强程序模块性 (modularity) 和代码可重用性的子例程 (subroutine) 函数可以通过它们自身递归地定义, 这是一种新颖的计算范型 最后但不是最不重要的是, 通过介绍函数, 我们将解释局部变量 ( 比如通常的块变量 ) 和全局内存变量 ( 比如静态类变量 ) 之间的区别 Java 在函数中只按值传递参数 这是与 C++ 之间的一个重大的根本区别,C++ 允许按值和按引用的变量传递 最后, 描述递归可以帮助我们解释 Java 的函数调用栈 (function call stack), 其中局部变量是临时分配的 3.2 声明和调用函数 3.2.1 原型化函数 函数应该总是在类 ( 目前是程序类 ) 体内声明 : 比如要声明一个函数 (function)f, 它接受 N 个类型分别为 Type1,,TypeN 的参数 arg1,, argn, 并且返回 TypeR 类型的结果, 则一般语法如下 :
56 程序设计与算法 (Java 语言版 ) static TypeR F(Type1 arg1, Type2 arg2,, TypeN argn) TypeR result; block_of_instructions; 过程是不返回任何结果的特殊函数 在 Java 中, 这是通过为函数返回类型使用 void 关键字指定的 因此, 过程的声明方式如下 : static void Proc(Type1 arg1, Type2 arg2,, TypeM argm) block_of_instructions; return; 最后一条指令语句 return; 可以省略 我们总是在过程 / 函数声明前面放置关键字 static:static void Proc, 在第 5 章讨论对象和方法时将解释这为什么是必要的 由于过程和函数将附加到类体上 ( 即封装到类中 ), 基本上就具有以下程序骨架 : 程序 3.1 用于定义静态函数的基本程序骨架 class ProgramSkeleton static TypeF F(Type1 arg1,, TypeN argn) TypeF result; // Description Block of instructions; static void Proc (Type1 arg1, Type2 arg2,, TypeM argm) block_instructions; return; public static void main(string[] arguments) 下面介绍一些具体的示例
第 3 章函数和递归函数 57 3.2.2 基本函数的示例 通过在 FunctionDeclaration.java 文本文件中输入以下代码, 创建一个示范程序类 FunctionDeclaration: 程序 3.2 用于定义和调用静态函数的基本示范类 class FunctionDeclaration static int square(int x) return x * x; static boolean isodd(int p) if ((p%2)==0) return false; else return true; static double distance(double x, double y) if (x>y) return x y; else return y x; static void display(double x, double y) System.out.println("("+x+","+y+")"); return; // return void public static void main (String[] args) display(3,2); display(square(2),distance(5,9)); int p=123124345; if (isodd(p)) System.out.println("p is odd"); else 编译并执行这段代码, 将得到 : (3.0,2.0) (4.0,4.0) p is odd System.out.println("p is even"); 如这个示例中所示, 函数和过程是定义在类 FunctionDeclaration 的作用域 (scope)
58 程序设计与算法 (Java 语言版 ) 中的 这些函数在 FunctionDeclaration 类的 main 函数中调用, 但这不是一种限制 : 也可以在其他函数的主体内调用这些函数 观察可知, 参数是它自身也可能包含函数调用的表达式 (expression), 如下面的示例所示 :display(square(2),distance(5,9)); 这第一个热身性质的示例显示函数 / 过程有助于编写代码子例程, 从而为代码模块性和代码重用提供了基础 代码重用有利于验证和校正程序, 可以把它们分解成基本的单元, 然后可以更容易地依次进行检验 由于函数封装在类中, 可以使用语法 OtherClass.F 调用在另一个类 ( 比如 OtherClass) 中声明的任意函数 F 在调用封装在 Math 类中的数学函数 ( 如 Math.cos(x);) 时, 我们已经使用过这种语法 Math 类是标准的 Java 应用程序编程接口 (application programming interface,api) 的大型集合的一部分, 它们是与 Java 开发工具包 (Java development kit, JDK) 一起安装的 如果函数是在同一个类的主体内声明的, 那么在调用该函数时可以省略类名 在我们的程序 FunctionDeclaration 中, 所有的函数都是这样 例如,display(3,2); 等价于函数调用 FunctionDeclaration.display(3,2); 观察可知, 程序类的 main 函数是默认过程 (default procedure), 它是在执行程序时调用的 3.2.3 一个更精心设计的示例 : 迭代式阶乘函数 试考虑对于任何给定的 n N +, 如何实现阶乘函数 : n! = 1 2 n= i 根据约定,0! = 1 由于阶乘函数不属于 Math 类的基本静态函数, 在名为 Toolbox 的工具箱类中编写自己的函数 factorial 使用一个 while 语句, 用于累加乘法 n 1, 如下所示 : 程序 3.3 实现阶乘函数 n! class Toolbox static int factorial(int n) int result=1; while(n>0) result*=n; // similar to result=result*n; n--; class ExampleFactorial n i= 1
第 3 章函数和递归函数 59 public static void main(string[] args) System.out.println("6!="+Toolbox.factorial(6)); 编译并执行这个程序, 得到 6!=720 3.2.4 带有条件语句的函数 3.2.2 节中以前的 distance 函数接受两个 double 类型的参数 x 和 y, 并在 double 类型的结果中返回它们的差的绝对值 回顾一下以前的代码 static double distance(double x, double y) double result; if (x>y) result=x-y; else result=y-x; 可以更简洁地将其重写如下 : static double distance(double x, double y) if (x>y) return x-y; else return y-x; 就使用分支条件语句 ( 如 if else 或 switch case 语句 ) 的函数或过程而言, 我们总是需要确保无论指令的工作流程是什么, 函数总会到达合适的 return 语句 编译器将检查所有这些不同的执行路径, 如果不满足这个性质, 编译器可能会发出 missing return statement 错误消息 例如, 利用下面这段错误的代码替换 distance 函数 : static double distance(double x, double y) double result; if (x>y) result=x-y; // forgot voluntarily the return statement else return y-x; 举另外一个例子, 考虑下面的代码段, 它使用了 switch case 语句 :
60 程序设计与算法 (Java 语言版 ) 程序 3.4 带有分支结构的函数 class FunctionWithConditionalStatement public static void main (String [] arguments) double x=math.e; System.out.println ("Choose function to evalute for x="+x) ; System.out.print ("(1) Identity, (2) Logarithm, (3) Sinus. Your choice?") ; int t=tc.lireint(); System.out.println ("F(x)="+F( t, x )); // Observe that here we deliberately chose the function to be declared after the main body public static double F(int generator, double x) double v=0.0; switch (generator) case 1: v=x; break; case 2: v=math.log(x); break; case 3: v=math.sin(x); break; return v; 这是类型化程序设计语言的一种非常好的特性, 用于检查具有合适返回类型 TypeR 的函数的所有返回路径 ( 最终通过隐式强制转换类型 ) 3.3 静态 ( 类 ) 变量 一旦介绍了函数, 就会看到变量声明潜在地出现在各自的函数体内, 这使得只能在 main 函数内发现它们的日子一去不复返了 这样, 变量作用域 (variable scope) 就被限制于由大括号定界的函数体 ; 不能从函数体外面访问这些变量 假定要统计给定函数被调用的次数 我们需要声明一类持久的变量, 可以把它附加到封装函数的类上 : 这些类型的持久变量被称为静态 (static) 变量 使用静态变量, 很容易统计函数调用的总次数, 如下面的代码所示 :
第 3 章函数和递归函数 61 程序 3.5 使用静态 ( 类 ) 变量的示例 class StaticVariable static int nbfunccalls=0; static int square(int x) nbfunccalls++; return x*x; static boolean isodd(int p) nbfunccalls++; if ((p%2)==0) return false; else return true; static double distance(double x, double y) double result; nbfunccalls++; if (x>y) result=x-y; else result=y-x; static void display(double x, double y) nbfunccalls++; System.out.println("("+x+","+y+")"); public static void main (String[] args) FunctionDeclaration.display(3,2); display(square(2),distance(5,9)); int p=123124345; if (isodd(p)) System.out.println("p is odd"); else System.out.println("p is even"); System.out.println("Total number of function calls:"+ nbfunccalls);
62 程序设计与算法 (Java 语言版 ) 运行这个程序, 完成后将得到以下消息 : Total number of function calls:4 静态变量是附加到类上的持久变量 这些静态变量存储在全局 (global) 内存中, 并且可以在任何时候从任何函数访问它们 因此, 静态变量被证明对于在封装进函数中的不同指令块之间共享信息非常有用 3.4 函数参数的按值传递 3.4.1 基本的参数传递机制 无论何时, 在 Java 中调用一个函数, 都会按顺序评估参数 ( 它们潜在地可能还包含其他函数调用的任意复杂的表达式 ) 如果必要,Java 编译器 javac 将对这些评估的表达式执行必要的隐式强制转换操作, 如果评估的表达式 (evaluated expression) 的类型与函数参数的定义类型不匹配, 就会发出错误消息 因此, 一般的函数调用原型化语法如下 : F(ExprArg1,, ExprArgN) 即使像通常那样利用普通的变量调用函数 F( 比如, 函数调用 F(var1,, varn)), 这些变量事实上也是基本表达式, 在这里将求出它们存储的值 一旦进入到函数体中, 将不再能够直接访问这些变量 因此, 执行函数调用实际上相当于执行这个函数, 其中绑定了参数变量和评估的表达式 : static TypeF F() Type1 arg1=exprarg1; TypeN argn=exprargn; // Body of the function
第 3 章函数和递归函数 63 3.4.2 局部内存和函数调用栈 在 Java 中, 在指令块中声明的变量全都是在对应函数的局部内存中创建和存储的 这种局部内存被称为函数调用栈 无论何时调用一个函数, 都会把局部变量所需的内存分配进函数栈 (function stack) 中, 图 3.1 中说明参数是按值 (value) 传递的 无论何时在当前函数体内调用另一个函数 ( 比如 G), 都适用相同的机制 : 首先, 分配用于存储在 G 的函数块中声明的所有块变量的局部内存, 并且按值传递参数 一旦完成了 G, 就会释放为其执行而分配的局部内存 这些不同级别的嵌套函数调用就产生了函数调用栈 (function call stack) 图 3.1 说明函数调用栈 : 函数变量被分配进局部内存栈中, 因此对其他函数不可见 按值传递机制在调用时把函数参数与各自的表达式值绑定在一起 程序 3.6 说明函数调用栈 class FunctionStack static double G(double x) double result; result=math.pow(x,2.5);
64 程序设计与算法 (Java 语言版 ) static double F(double x) double result; result=1.0+g(x*x); public static void main (String[] args) double y; y=f(5.0); System.out.println("y="+y); 例如, 考虑上面的程序, 函数调用栈演化如下 : 步骤 1 2 3 4 5 6 7 调用 调用 调用 完成 完成 完成 动作 : 运行 main F G G F main 函数栈 Ø main F main G F main F main main Ø 注意 : 既然参数是按值传递的, 那么调用函数的局部变量将不会改变 为了强调这一点, 考虑下面的娱乐性示例程序 : 程序 3.7 按值传递不会改变调用函数的局部变量 class PassByValue static void F(double x) x=3; // Here is the catch. Take care of pass-by-value. System.out.println ("Before exiting F, value of x:"+x); public static void main (String [] args) double x=5; F(x); System.out.println ("value of x:"+x);