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

题目

用递归求斐波那契第 n 项

思路

本题用递归求斐波那契第 n 项。

递归边界：n<=2 返回 1；否则返回 fib(n-1)+fib(n-2)。规模稍大时重复计算很多，本题 n 较小可接受；可对照迭代或记忆化写法。

解题分析

斐波那契递归直接按定义写，但重复计算大量子问题，n 稍大就慢。迭代用两个变量滚动更新，时间 O(n)，空间 O(1)，线上练习更稳。

完整程序

#include <stdio.h>

static long long fib(int n)
{
    if (n <= 2) {
        return 1;
    }
    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