c语言实现一个递归算法
下面给你几个经典的 C 语言递归示例,附带讲解。
递归核心:函数自己调用自己,必须有终止条件(基线条件),否则无限递归栈溢出
示例1:求阶乘(最简单)
公式: n! = \begin{cases} 1 & n=0 \text{ 或 } n=1 \ n \times (n-1)! & n>1 \end{cases}
#include <stdio.h>
// 递归求阶乘
long long fact(int n)
{
// 终止条件
if (n == 0 || n == 1)
return 1;
// 递归调用
return n * fact(n - 1);
}
int main(void)
{
int n = 5;
printf("%d! = %lld\n", n, fact(n));
return 0;
}
输出:
5! = 120
示例2:斐波那契数列
F(n)= \begin{cases} 1 & n=1,;n=2 \ F(n-1)+F(n-2) & n>2 \end{cases}
#include <stdio.h>
int fib(int n)
{
if (n == 1 || n == 2)
return 1;
return fib(n - 1) + fib(n - 2);
}
int main(void)
{
for (int i = 1; i <= 10; i++)
{
printf("%d ", fib(i));
}
return 0;
}
输出:1 1 2 3 5 8 13 21 34 55
示例3:递归遍历打印 1~n
#include <stdio.h>
void printN(int n)
{
if (n < 1)
return;
printN(n - 1);
printf("%d ", n);
}
int main(void)
{
printN(5);
return 0;
}
示例4:递归反转字符串
#include <stdio.h>
void reverse(char *s)
{
if (*s == '\0')
return;
reverse(s + 1);
putchar(*s);
}
int main(void)
{
char str[] = "hello";
reverse(str);
return 0;
}
递归要点总结
- ✅ 基线条件(出口):先写终止判断,防止死递归
- ✅ 递归式子:把问题拆成更小的同类型子问题
- ⚠️ 缺点:递归深度大时容易栈溢出;斐波那契朴素递归存在大量重复计算
关于 LearnKu