3.3 函数调用机制
一个C++程序是由若干个函数构成的。每个函数都是独立定义的模块。函数之间可以互相调用。函数调用关系如图3.4所示。图中箭头表示在函数体内出现对另一个函数的调用。
图3.4 函数调用关系
main函数可以调用各个自定义函数和库函数，各个自定义函数可以互相调用。每个应用程序只有一个main函数，由操作系统启动。函数之间可以互相调用，可以嵌套调用。例如，在图3.4中，main函数调用函数fun2，在fun2函数体中又调用fun5，这种方式称为嵌套调用。函数可以自身调用，称为递归调用。图3.4中，fun7在函数体内出现自身调用，称为直接递归。fun4函数中调用fun1，而fun1中又调用了fun4，称为间接递归。
函数之所以能够正确地实现调用，是由于系统设置一个先进后出堆栈进行调用信息管理。执行代码出现函数调用时，系统首先把调用现场各种参数、返回后要继续执行的代码地址，压入堆栈；然后传递参数，把控制权交给被调用函数；被调用函数执行结束，堆栈弹出现场参数，控制权交还调用函数继续执行。
3.3.1 嵌套调用
函数嵌套调用的代码结构如图3.5所示。
图3.5 函数嵌套调用的代码结构
图3.5表示，在main函数中调用fa函数，在fa函数中调用fb函数，在fb函数中调用fc函数。main函数由操作系统调用，首先把操作系统的运行状态、返回地址及 main 函数的参数压入堆栈；在main函数中，调用fa，把main的运行状态、返回地址及fa的参数压入堆栈……一直到fc执行结束，堆栈弹出栈顶的第一层信息，接收fc的执行结果，恢复fb的执行现场，继续执行fb的后续代码；当fb执行结束后，堆栈又弹出顶层信息，接收fb的执行结果，恢复fa的执行现场，继续执行fa的后续代码；一直到堆栈弹空，程序执行结束。
函数调用信息管理堆栈如图3.6所示。
图3.6 函数调用信息管理堆栈
【例3-18】已知
式中，
，求g(2.5, 3.4)，g(1.7, 2.5)和g(3.8, 2.9)的值。
程序设计按照功能划分和代码重用的原则，首先定义f函数，通过g函数调用f函数，实现函数的完整功能。main函数向g传递实际参数的数据，完成计算。
#include<iostream>
#include<cmath>
using namespace std;
double f(double);
double g(double, double);
int main()
{ cout<<"g(2.5,3.4)="<<g(2.5,3.4)<<endl;
cout << "g(1.7, 2.5) = " << g(1.7, 2.5) << endl;
cout << "g(3.8, 2.9) = " << g(3.8, 2.9) << endl;
}
double g(double x, double y)
{ if(x<=y) return f(x+y)/(f(x)+f(y));
else return f(x-y)/(f(x)+f(y));
}
double f(double t)
{ return(1+exp(-t))/(1+exp(t)); }
程序运行结果：
g(2.5, 3.4) = 0.0237267
g(1.7, 2.5) = 0.0566366
g(3.8, 2.9) = 5.25325
3.3.2 递归调用
递归是推理和问题求解的一种强有力方法，原因在于，许多对象，特别是数学研究对象，具有递归的结构。简单地说，如果通过一个对象自身的结构来描述或部分描述该对象，就称为递归。
递归定义使人们能够用有限的语句描述一个无穷的集合。C++语言允许一个函数体中出现调用自身的语句，称为直接递归调用。也允许被调用的另一个函数又反过来调用原函数，称为间接递归调用。这种功能为递归结构问题提供了求解的实现手段，使程序语言的描述与问题的自然描述完全一致，因而使程序易于理解、易于维护。
下面通过一个简单的例子说明递归函数的构成规律和执行过程。
【例3-19】使用递归函数编程序求n!。
根据数学知识，非负整数n的阶乘为：
n!=n×(n-1)×(n-2)×…×1
其中，0! = 1。
当n≥0时，阶乘可以用循环迭代（非递归）计算：
fact = 1;
for (int k = n; k >= 1; k--)
fact *= k;
也可以用另一种递归形式定义阶乘：
阶乘的递归定义把问题分解为两部分：一部分用已知的参数n作为被乘数，另一部分使用原来的阶乘定义作为乘数。不过，乘数(n-1)! 的问题规模缩小了。
由定义有，(n-1)! = (n-1) × (n-2)!，问题规模进一步缩小，从而产生越来越小的问题，最后归结到基本情况，0!=1。C++函数调用能够识别并处理这种基本情况，向前一个函数调用返回结果，并回溯一系列中间结果，直到把最终结果返回给调用函数。
以下程序在main函数中调用求阶乘的递归函数。
#include<iostream>
using namespace std;
long fact(int n)
{ if(n==0) return 1; //递归终止情况
else return n*fact(n-1); //递归调用
}
int main()
{ int n;
cout << "Enter n (>=0) : ";
cin >> n;
cout << n << "! = " << fact(n) << endl;
}
递归函数执行由递推和回归两个过程完成。假如执行main函数时，输入n的值为3，则函数调用fact(3)的递推和回归过程如图3.7所示。
图3.7 函数调用fact(3)的递推过程和回归过程
递归调用之所以能够实现，关键是系统使用堆栈来保存函数调用中的传值参数、局部变量和函数调用后的返回地址。函数自身调用进行递推：系统把有关参数和地址压进堆栈，一直递推到满足终止条件，找到问题的最基本模式为止。然后进行回归：系统从堆栈中逐层弹出有关参数和地址，执行地址所指向的代码，一直到栈空为止，得到问题的解。
递归调用与一般函数调用，堆栈管理的操作过程是一致的。不同的是，函数的自身调用就像是产生多个正在运行（等待结束）的相同函数副本。如果这种调用不能终止并产生回归，将是程序十分严重的错误。
构成递归函数有两个基本要素：
· 描述问题规模逐步缩小的递归算法；
· 描述基本情况的递归终止条件。
· 在fact函数中，递归调用的语句为：
t = n * fact(n-1);
由调用参数n-1，使问题规模逐步缩小，直至到达递归调用终止条件：
n==0
返回基本情况值1。
在程序中，递归算法和递归条件通常用条件语句表达。递归调用可以出现在执行语句中，也可以出现在判断表达式中。
【例3-20】求正整数a和b的最大公约数。
a和b的最大公约数，就是能同时整除a和b的最大整数。从数学上可知，求a和b的最大公约数等价于求b与a除以b的余数（即a % b）的最大公约数。具体的算法可以用递归公式表示为：
例如，按上述递归公式求a=24与b=16的最大公约数的过程为：
因为b=24＞0，
所以求a=24与b=16的最大公约数转换为求a=16与b=(24 % 16)=8的最大公约数；
因为b=8＞0，
所以求a=16与b= 8的最大公约数转换为求a=8与b=(16 % 8)=0的最大公约数；
因为b=0，
所以a=8与b=0的最大公约数为8，即24和16的最大公约数是8。
按上述递归公式编写程序如下：
#include<iostream>
using namespace std;
int gcd(int, int);
int main()
{ int a,b;
cout << "input a (>=0) : ";
cin >> a;
cout << "input b (>=0) : ";
cin >> b;
cout << "gcd (" << a << ", " << b << ") = " << gcd(a, b) << endl;
}
int gcd(int a, int b)
{ int g;
if(b==0) g=a;
else g=gcd(b,a%b);
return g;
}
【例3-21】斐波那契数列。
斐波那契（Fibonacci）数列的第1项为0，第2项为1，后续的每一项是前面两项的和。该数列两项的比例趋于一个常量：1.618…，称为黄金分割。数列形如：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55…
斐波那契数列可以用递归定义：
Fibonacci(0) = 0
Fibonacci(1) = 1
Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)
根据递归定义，可以直接写出求斐波那契数列第n项的函数：
#include<iostream>
using namespace std;
long fibonacci(long);
int main()
{ long value,n;
cout << "Enter an integer : ";
cin >> n;
value = fibonacci(n);
cout << "Fibonacci(" << n << ") = " << value << endl;
}
long fibonacci(long n)
{ if(n==0||n==1) return n;
else return fibonacci(n-1)+fibonacci(n-2);
}
在main函数中调用fibonacci不是递归调用，但后续所有调用fibonacci函数都是递归的。每次调用fibonacci时，立即测试递归条件（n等于0或等于1）。如果是基本情况，则返回n。如果n>1，则递归步骤产生两个递归调用，分别解决原先调用fibonacci问题的一个简化问题。如图3.8所示为用fibonacci函数求fibonacci(3)的值的递归调用过程，图中将fibonacci缩写为fib。
图3.8 fibonacci数列的递归调用过程
前面几个例子，都可以用迭代方式来改写函数。但有一些问题，必须用递归方式解决。汉诺塔问题就是一个递归算法的经典问题。
【例3-22】汉诺塔问题。
传说印度的主神梵天在一个黄铜板上插了3根宝石针，并在其中一根针上从上到下按从小到大的顺序串上了 64 个金片。梵天要求僧侣们把金片全部移动到另一根针上去，规定每次只能移动一片，且不许将大片压在小片上。移动时可以借助第三根针暂时存放盘子。梵天说，如果这64个金片全部移至另一根针上时，世界就会在一声霹雳之中毁灭。这就是汉诺塔。如图 3.9 所示为8个金片的汉诺塔示意。
如何让计算机模拟这个游戏呢？为了便于说明，下面用精确的语言加以表述。我们称移动 n个金片的问题为n阶汉诺塔问题。以A、B、C代表3根宝石针，把金片从小到大按顺序编号为1～n，并引入记号：
Move(n,A,B,C)
表示n个金片从A移到C，以B为过渡。
注意，要把n个金片从A移到C，必须把最大的金片n从A移到C。为此，首先要把金片1～n-1搬到B。
图3.9 8个金片的汉诺塔示意
金片n移到C后就不必再移动了。显然，一阶汉诺塔问题：
Move(1,A,B,C)
即把一个金片直接从A移到C，是一个可以直接解决的问题，表示为：
A→C
剩下的问题是把n-1个金片从B移到C（以A为过渡）。
于是，求解n阶汉诺塔问题变成了求解两个n-1阶汉诺塔问题，问题降了一阶。
由此可以看到，这是一个典型的递归问题。为了解决 n 阶汉诺塔问题 Move(n,A,B,C)，问题可表述为：
Move(n-1, A, C, B);
A →C; //Move(1，A,B,C)
Move(n-1, B, A, C);
递归终止条件为 n=1。遵循降阶的步骤，经过有限步后必定能达到 n=1。这样就可以使用递归函数来求解此问题了。
#include<iostream>
using namespace std;
void Move(int n,char a, char b, char c)
{ if(n==1) //只有一个金片
cout << a << " --> " << c << endl;
else //否则
{ Move(n-1,a,c,b); //把n-1个金片从a移到b，以c为过渡
cout<<a<<"-->"<<c<<endl; //从a移一个盘子到c
Move(n-1, b, a, c); //把n-1个盘子从b移到c，以a为过渡
}
}
int main()
{ int m;
cout << "Input the number of disks: " << endl;
cin >> m;
Move(m, 'A', 'B', 'C');
}