C 语言第52题：用递归求斐波那契第 n 项

题目

编写递归函数求解斐波那契数列第 n 项的值（数列前两项为 1, 1，后续项为前两项之和）。

输入格式：一行输入一个正整数 n。

输出格式：输出一个整数，表示斐波那契数列第 n 项的值，末尾换行。

数据范围与约定：1 ≤ n ≤ 30。

思路与算法

1. 递归基（终止条件）
当 n == 1 || n == 2 时，递归直接返回基准值 1。

2. 递归推导式
当 n > 2 时，递归调用 fib(n-1) + fib(n-2)。注意朴素递归存在大量的重叠子问题计算，调用树呈指数级 O(2ⁿ)，只适用于 n 较小的场景。

完整程序

#include <stdio.h>

// 递归求斐波那契数：基础终止条件为前两项 F(1) = F(2) = 1
static long long fib(int n)
{
    if (n <= 2) {
        return 1;
    }
    // 递归关系式：F(n) = F(n-1) + F(n-2)
    return fib(n - 1) + fib(n - 2);
}

int main(void)
{
    int n;
    if (scanf("%d", &n) != 1 || n < 1) {
        return 1;
    }
    printf("%lld\n", fib(n));
    return 0;
}

运行示例

输入：

10

输出：

55

其它写法

下面每种写法都是完整程序，输入输出格式与正文一致，便于对照。

迭代求第 n 项

程序：

#include <stdio.h>

int main(void)
{
    int n;
    if (scanf("%d", &n) != 1 || n < 1) {
        return 1;
    }
    long long a = 1, b = 1;
    for (int i = 3; i <= n; i++) {
        long long c = a + b;
        a = b;
        b = c;
    }
    printf("%lld\n", n <= 2 ? 1 : b);
    return 0;
}

输入：

10

输出：

55