题解 | 递归-斐波那契数列 | 不死神兔问题

#include <iostream>
using namespace std;

int getSum(int n);

int main() {

    int n;
    cin >> n;

    cout << getSum(n) << endl;

    return 0;
}

int getSum(int n) {

    // write your code here......
    if(n==1 || n==2){
        return 1;
    }
    return getSum(n-1) + getSum(n-2);
    
}

递归的核心就是两点，

✔ 条件 1：必须有【递归出口】（终止条件）

你的代码里：if(n==1 || n==2) return 1;

就是递归出口，意思是：当问题小到「求第 1/2 项」时，不用再拆解了，直接返回确定的结果 1，防止无限递归。

✔ 条件 2：必须有【递推公式】（缩小问题规模）

你的代码里：return getSum(n-1)+getSum(n-2);

就是递推公式，意思是：求第 n 项的问题，拆解成「求 n-1 项」和「求 n-2 项」两个更小的问题，问题规模在一步步变小，最终一定会走到递归出口。

其实就是到终止条件后得到最小单位的值，倒回来逐个推导前一个函数的值，再一个一个去代入计算。

比如：

累加和的递归逻辑

• 递归出口：n=1 时，返回 1（1 的和就是 1）
• 递推公式：sum (n) = n + sum (n-1) （n 的和 = n + 1~n-1 的和）

n=5 时，执行流程是：getSum(5) =5+getSum(4) → getSum(4)=4+getSum(3) → getSum(3)=3+getSum(2) → getSum(2)=2+getSum(1) → getSum(1)=1