Java第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 较小的场景。

完整程序

import java.util.Scanner;

public class Main {
    // 递归求解斐波那契数列第 n 项
    public static int fib(int n) {
        if (n <= 2) {
            return 1;
        }
        return fib(n - 1) + fib(n - 2);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(fib(n));
    }
}

运行示例

输入：

10

输出：

55