发布日期:2015-12-22 09:20 来源: 标签: 编程语言 C++教程 C++函数 C++函数递归调用
在调用一个函数的过程中又出现直接或间接地调用该函数本身,称为函数的递归(recursive)调用。本章我们主要学习函数递归调用,下面我们就做一下具体讲解,希望大家多多支持中国站长网络学院。
在调用一个函数的过程中又出现直接或间接地调用该函数本身,称为函数的递归(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函数。

从图上可以看到,这两种递归调用都是无终止的自身调用。显然,程序中不应出现这种无终止的递归调用,而只应出现有限次数的、有终止的递归调用,这可以用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个人年龄的过程。

可以写出以下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.12所示。

例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
许多问题既可以用递归方法来处理,也可以用非递归方法来处理。在实现递归时,在时间和空间上的开销比较大,但符合人们的思路,程序容易理解。

相关评论

专题信息
    C++是在C语言的基础上开发的一种面向对象编程语言,应用广泛。C++支持多种编程范式 --面向对象编程、泛型编程和过程化编程。最新正式标准C++于2014年8月18日公布。 其编程领域众广,常用于系统开发,引擎开发等应用领域,是至今为止最受广大程序员受用的最强大编程语言之一,支持类:类、封装、重载等特性! 本教程从基础讲解了C++语言,希望对大家有所帮助,望多多支持中国站长网络学院。