C++函数的递归调用

时间：2014-10-15 14:55 点击：次

在调用一个函数的过程中又出现直接或间接地调用该函数本身，称为函数的递归(recursive)调用。C++允许函数的递归调用。例如：

int f(int x)
{
int y, z;
z=f(y); //在调用函数f的过程中，又要调用f函数
return (2*z);
}

以上是直接调用本函数，见图4.9。图4.10表示的是间接调用本函数。在调用f1函数过程中要调用f2函数，而在调用f2函数过程中又要调用f1函数。

图 4.9

图 4.10

从图上可以看到，这两种递归调用都是无终止的自身调用。显然，程序中不应出现这种无终止的递归调用，而只应出现有限次数的、有终止的递归调用，这可以用if语句来控制，只有在某一条件成立时才继续执行递归调用，否则就不再继续。包含递归调用的函数称为递归函数。【例4.10】有5个人坐在一起，问第5个人多少岁?他说比第4个人大两岁。问第4个人岁数，他说比第3个人大两岁。问第3个人，又说比第2个人大两岁。问第2个人，说比第1个人大两岁。最后问第1个人，他说是10岁。请问第5个人多大？每一个人的年龄都比其前1个人的年龄大两岁。即： age(5)=age(4)+2 age(4)=age(3)+2 age(3)=age(2)+2 age(2)=age(1)+2 age(1)=10 可以用式子表述如下： age(n)=10 (n=1) age(n)=age(n-1)+2 (n>1) 可以看到，当n>1时，求第n个人的年龄的公式是相同的。因此可以用一个函数表示上述关系。图4.11表示求第5个人年龄的过程。

图 4.11

可以写出以下C++程序，其中的age函数用来实现上述递归过程。

#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时，年龄为10
else c=age(n-1)+2; //当n>1时，此人年龄是他前一个人的年龄加2
return c; //将年龄值带回主函数
}

运行结果如下： 18 【例4.11】用递归方法求n!。求n!可以用递推方法，即从1开始，乘2，再乘3……一直乘到n。求n!也可以用递归方法，即5!=4!×5，而4!=3!×4，…，1!=1。可用下面的递归公式表示： n! = 1 (n=0, 1) n * (n-1)! (n>1) 有了例4.10的基础，很容易写出本题的程序：

#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的值作为函数值返回
}

运行情况如下： please input an integer：10↙ 10!=3628800 许多问题既可以用递归方法来处理，也可以用非递归方法来处理。在实现递归时，在时间和空间上的开销比较大，但符合人们的思路，程序容易理解。

来源：未知/所属分类：基础教程/更新时间：2014-10-15 14:55

[返回列表]

顶一下

(0)

踩一下

(0)

上一篇：C++函数的嵌套调用

下一篇：C++局部变量和全局变量

C++函数的递归调用

最新内容

热点内容