题目

用递归求斐波那契第 n 项

思路

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

解题分析

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

完整程序

import java.io.*;

public class Main {
    public static void main(String[] args) {
        int n = 10;
        long a = 1, b = 1, c = 1;
        for (int i = 3; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        System.out.println(n <= 2 ? 1 : c);
    }
}

运行示例

输出：

55