递归算法讲解·题目+题解

原题链接：7972.【递归】斐波那契数列

米乐

2025-08-17 21:03:12

发布于：广东

2阅读

0回复

0点赞

OK欢迎回来
这道题想必大家都做过，但是这道题要用递归做，我们慢慢来看

这个题目是应用场景中的第4个场景，也是以后学前缀和的基础，思路也就是第 a[i] 个数等于第 a[i-1] 的数加上第a[i-2]的数，其中第1、2个数是要赋值为 1

用代码表示就是 a[i] = a[i-1] + a[i-2];

思路知道了，题就好做了

首先先处理输入输出：

int main() {
    int n;
    cin >> n;
}

然后处理递归函数：

long long f(long long n) {  //输入结束条件。俗话说，3年oi一场空，不开long long见祖宗，所以要开long long
    if (n == 1 || n == 2) {     //第1、2个数是要赋值为 1
        return 1; 
    }
    return f(n - 1) + f(n - 2);
}

最后调用递归：

#include <bits/stdc++.h>
using namespace std;
long long f(long long n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    return f(n - 1) + f(n - 2);
}
int main() {
    int n;
    cin >> n;
    cout << f(n);
}