C++函数的嵌套调用
C++不允许对函数作嵌套定义，也就是说在一个函数中不能完整地包含另一个函数。在一个程序中每一个函数的定义都是互相平行和独立的。
虽然C++不能嵌套定义函数，但可以嵌套调用函数，也就是说，在调用一个函数的过程中，又调用另一个函数。
在程序中实现函数嵌套调用时，需要注意的是：在调用函数之前，需要对每一个被调用的函数作声明(除非定义在前，调用在后)。
【例】用弦截法求方程f(x)=x3-5x2+16x-80=0的根。
这是一个数值求解问题，需要先分析用弦截法求根的算法。根据数学知识，可以列出以下的解题步骤：
1) 取两个不同点x1，x2，如果f(x1)和f(x2)符号相反，则(x1，x2)区间内必有一个根。如果f(x1)与f(x2)同符号，则应改变x1，x2，直到f(x1)， f(x2)异号为止。注意x1?x2的值不应差太大，以保证(x1，x2)区间内只有一个根。
2) 连接(x1， f(x1))和(x2， f(x2))两点，此线(即弦)交x轴于x，见图。
x点坐标可用下式求出：
再从x求出f(x)。
3) 若f(x)与f(x1)同符号，则根必在(x， x2)区间内，此时将x作为新的x1。如果f(x)与f(x2)同符号，则表示根在( x1，x)区间内，将x作为新的x2。
4) 重复步骤 (2) 和 (3)， 直到 |f(x)|<ξ为止， ξ为一个很小的正数， 例如10-6。此时认为 f(x)≈0。
这就是弦截法的算法，在程序中分别用以下几个函数来实现以上有关部分功能：
1) 用函数f(x)代表x的函数:x3-5x2+16x-80。
2) 用函数xpoint (x1,x2)来求(x1,f(x1))和(x2,f(x2))的连线与x轴的交点x的坐标。
3) 用函数root(x1,x2)来求(x1,x2)区间的那个实根。显然，执行root函数的过程中要用到xpoint函数，而执行xpoint函数的过程中要用到f函数。
根据以上算法，可以编写出下面的程序：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
#include <iostream>#include <iomanip>#include <cmath>using namespace std;double f(double); //函数声明double xpoint(double, double); //函数声明double root(double, double); //函数声明int main( ){ double x1,x2,f1,f2,x; do { cout<<"input x1,x2:"; cin>>x1>>x2; f1=f(x1); f2=f(x2); } while(f1*f2>=0); x=root(x1,x2); cout<<setiosflags(ios::fixed)<<setprecision(7); //指定输出7位小数 cout<<"A root of equation is "<<x<<endl; return 0;}double f(double x) //定义f函数,以实现f(x){ double y; y=x*x*x-5*x*x+16*x-80; return y;}double xpoint(double x1, double x2) //定义xpoint函数,求出弦与x轴交点{ double y; y=(x1*f(x2)-x2*f(x1))/(f(x2)-f(x1)); //在xpoint函数中调用f函数 return y;}double root(double x1, double x2) //定义root函数,求近似根{ double x,y,y1; y1=f(x1); do { x=xpoint(x1,x2); //在root函数中调用xpoint函数 y=f(x); //在root函数中调用f函数 if (y*y1>0) { y1=y; x1=x; } else x2=x; }while(fabs(y)>=0.00001); return x;} |
运行情况如下：
|
1
2
|
input x1, x2:2.5 6.7↙A root of equation is 5.0000000 |
对程序的说明：
1) 在定义函数时，函数名为f，xpoint和root的3个函数是互相独立的，并不互相从属。这3个函数均定为双精度型。
2) 3个函数的定义均出现在main函数之后，因此在main函数的前面对这3个函数作声明。
习惯上把本程序中用到的所有函数集中放在最前面声明。
3) 程序从main函数开始执行。
4) 在root函数中要用到求绝对值的函数fabs，它是对双精度数求绝对值的系统函数。它属于数学函数库，故在文件开头用#include <cmath>把有关的头文件包含进来。
C++函数的递归调用
在调用一个函数的过程中又出现直接或间接地调用该函数本身，称为函数的递归(recursive)调用。C++允许函数的递归调用。例如：
|
1
2
3
4
5
6
|
int f(int x){ int y, z; z=f(y); //在调用函数f的过程中，又要调用f函数 return (2*z);} |
以上是直接调用本函数，见下面的图。
下图表示的是间接调用本函数。在调用f1函数过程中要调用f2函数，而在调用f2函数过程中又要调用f1函数。
从图上可以看到，这两种递归调用都是无终止的自身调用。显然，程序中不应出现这种无终止的递归调用，而只应出现有限次数的、有终止的递归调用，这可以用if语句来控制，只有在某一条件成立时才继续执行递归调用，否则就不再继续。
包含递归调用的函数称为递归函数。
【例】有5个人坐在一起，问第5个人多少岁?他说比第4个人大两岁。问第4个人岁数，他说比第3个人大两岁。问第3个人，又说比第2个人大两岁。问第2个人，说比第1个人大两岁。最后问第1个人，他说是10岁。请问第5个人多大？
每一个人的年龄都比其前1个人的年龄大两岁。即：
|
1
2
3
4
5
|
age(5)=age(4)+2age(4)=age(3)+2age(3)=age(2)+2age(2)=age(1)+2age(1)=10 |
可以用式子表述如下：
|
1
2
|
age(n)=10 (n=1)age(n)=age(n-1)+2 (n>1) |
可以看到，当n>1时，求第n个人的年龄的公式是相同的。因此可以用一个函数表示上述关系。图4.11表示求第5个人年龄的过程。
可以写出以下C++程序，其中的age函数用来实现上述递归过程。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
#include <iostream>using namespace std;int age(int);//函数声明int main( )//主函数{cout<<age(5)<<endl;return 0;}int age(int n)//求年龄的递归函数{int c; //用c作为存放年龄的变量if(n==1) c=10; //当n=1时，年龄为10else c=age(n-1)+2; //当n>1时，此人年龄是他前一个人的年龄加2return c; //将年龄值带回主函数} |
运行结果如下：
|
1
|
|
【例】用递归方法求n!。
求n!可以用递推方法，即从1开始，乘2，再乘3……一直乘到n。求n!也可以用递归方法，即5!=4!×5，而4!=3!×4，…，1!=1。可用下面的递归公式表示：
|
1
2
|
n! = 1 (n=0, 1)n * (n-1)! (n>1) |
有了例4.10的基础，很容易写出本题的程序：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
#include <iostream>using namespace std;long fac(int);//函数声明int main( ){ int n;//n为需要求阶乘的整数 long y; //y为存放n!的变量 cout<<"please input an integer ："; //输入的提示 cin>>n; //输入n y=fac(n);//调用fac函数以求n! cout<<n<<"!="<<y<<endl; //输出n!的值 return 0;}long fac(int n) //递归函数{ long f; if(n<0) { cout<<"n<0,data error!"<<endl; //如果输入负数,报错并以-1作为返回值 f=-1; } else if (n==0||n==1) f=1; //0!和1!的值为1 else f=fac(n-1)*n;//n>1时,进行递归调用 return f;//将f的值作为函数值返回} |
运行情况如下：
|
1
2
|
please input an integer：10↙10!=3628800 |
许多问题既可以用递归方法来处理，也可以用非递归方法来处理。在实现递归时，在时间和空间上的开销比较大，但符合人们的思路，程序容易理解。
