c语言实现一个递归算法

AI摘要
内容为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;
}

递归要点总结

  1. ✅ 基线条件(出口):先写终止判断,防止死递归
  2. ✅ 递归式子:把问题拆成更小的同类型子问题
  3. ⚠️ 缺点:递归深度大时容易栈溢出;斐波那契朴素递归存在大量重复计算
六月的风
Junwind
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!