在调用一个函数的过程中又出现直接或间接地调用该函数本身,称为函数的递归调用。C语言的特点之一就在于允许函数的递归调用。例如
int f(int x)
{
int y,z;
z=f(y);
return (2*z);
}
这是在调用函数f的过程中,又要调用f函数,这是直接调用本函数。
如果在调用f1函数过程中要调用f2函数,而在调用f2函数过程中又要调用f1函数,就是间接调用本函数。
这两种递归调用都是无终止的自身调用。显然,程序中不应出现这种无终止的递归调用,应该出现有限次数的、有终止的递归调用,这可以用if语句来控制,只有在某一条件成立时才继续执行递归调用;否则就不再继续。
【例题1】
有5个学生坐在一起,问第5个学生多少岁,他说比第4个学生大2岁。问第4个学生多少岁,他说比第3个学生大2岁。问第3个学生多少岁,他说比第2个学生大2岁。问第2个学生多少岁,他说比第1个学生大2岁。最后问第1个学生,他说他是10岁。求第5个学生多少岁。
【思路】
要求第5个学生的年龄,就必须知道第4个学生的年龄,而第4个学生的年龄也不知道,要求第4个学生的年龄就必须先知道第3个学生的年龄,而第3个学生的年龄取决于第2个学生的年龄,而第二个学生的年龄取决于第1个学生的年龄,第1个学生的年龄是10。而且每一个学生的年龄都比其前一个学生的年龄大2。即
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)
显然这是一个递归问题,求解这个问题分为两个阶段:第一阶段是“回溯”,即将第5个学生的年龄表示为第4个学生年龄的函数,表示为:Age(5)=Age(4)+2。而第4的学生的年龄仍然不知道,还要“回溯”到第3个学生的年龄,表示为:Age(4)=Age(3)+2…直到第1个学生的年龄。此时Age(1)已知等于10,不必再向前回溯了。然后开始第二阶段,采用递推方法,从第1个学生的已知年龄推算出第2个学生的年龄(12岁),从第2个学生的年龄推算出第3个学生的年龄(14岁)…一直推算出第5个学生的年龄(18岁)为止。
所以,一个递归问题可以分为“回溯”和“递推”两个阶段。要经历若干步才能求出最后的值。显而易见,如果要求递归过程不是无限制的进行下去,必须具有一个结束递归过程的条件。
【代码实现】
int Age(int n)
{
int age;
if(n==1)
age=10;
else
age=Age(n-1)+2;
return age;
}
int main()
{
int n=5;
int age;
age=Age(n);
printf("第5个学生%d岁", age);
return 0;
}
【结果】
【例题2】
用递归方法求n!。
【思路】
求n!可以用递推方法,即从1开始,乘2,再乘3…一直乘到n。递推法的特点是从一个已知的事实(如1!=1
)出发,按一定规律推出下一个事实(如2!=2*1!
)再从这个新的已知的事实出发,再向下推出一个新的事实(如3!=3*2!
)。n!=n*(n-1)!
求n!也可以用递归方法,即5!=4!*5
,而4!=3!*4
,… ,1!=1
。可以用下面的递归公式表示:
n!=1 , (n=0,1)
n!=n*(n-1)! , (n>1)
【代码实现】
int fac(int n)
{
int x;
if (n < 0)
{
x = 0;
}
else if (n == 0 || n == 1)
{
x = 1;
}
else
{
x = n * fac(n - 1);
}
return x;
}
int main()
{
int n;
printf("输入要求阶乘的数字:\n");
scanf("%d", &n);
int x;
x = fac(n);
if (x == 0)
{
printf("负数没有阶乘\n");
}
else
printf("%d的阶乘为%d\n", n,x);
return 0;
}
【结果】
注意:
如果输入13, 企图求13!,是得不到预期结果的,因为求出的结果超过了int型数据的最大值。可将x和fac函数定义为float或者double型。
今天的文章C语言 函数的递归调用分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/30177.html