C语言中的递归函数的简单应用
2024-01-01 08:32:33
递归函数
简介
递归函数是指在函数内部调用自身的函数。这种函数可以通过不断调用自身来解决问题,通常用于解决可以被分解为相似子问题的情况。
注意
- 递归函数需要有终止条件,否则会导致无限循环,消耗大量资源。
- 递归函数的性能可能不如迭代函数,因此在处理大规模数据时需要理性使用。
- 递归函数层数太多很有可能会导致栈溢出,特别是在处理大规模数据时需要注意堆栈的大小。
- 递归函数要注意内存的使用,避免出现内存泄漏的情况。
使用示例
求n的阶乘
分析问题:
求 n!是一个机械化的连续的单一过程,由此我们可以考虑递归函数
代码示例:
long long Fact(int n)
{
if (n < 0)
return -1;//错误条件
else if (n == 0 || n == 1)//基本条件
return 1;
else
return n * Fact(n-1);
}
这里我们使用了long long
型整型尽可能的避免数据过大而造成的内存溢出。
同时,我们也应该控制递归的次数,防止栈溢出。
求Fibonacci数列
分析问题:
斐波那契数列是一个经典的数学问题,它是一个无限数列,以0和1开始,后续的每一项都是前两项的和。斐波那契数列的前几项为:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …依次类推。
此函数的运算方法单一且连续,所以可以考虑递归函数
代码示例
long long Fib(int n)
{
if (n <= 0)
return -1;//错误条件
else if (n == 1)
return 0;
else if (n == 2)
return 1;//基本条件
else
return Fib(n - 1)+Fib(n-2);
}
求最大公约数
分析问题:
求最大公约数的方法有两种:辗转相减法和辗转相除法。无论是哪一种方法,其实都是多次且单一的运算,所以也可以用递归函数。
代码一:辗转相减法:
int gcd(int a, int b)
{
if (a == b)
{
return a;
}
if (a > b)
{
return gcd(a - b, b);
} else
{
return gcd(a, b - a);
}
}
代码二:辗转相除法:
int gcd(int a, int b)
{
if (b == 0)
{
return a;
}
else
{
return gcd(b, a % b);
}
}
其实如果我们一步步调试代码(或手动进行递归计算),那么我们可以发现辗转相除法比辗转相减法的递归次数少,所以我们优先选择辗转相除法。
文章来源:https://blog.csdn.net/2301_79896143/article/details/135322011
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!