递归

递归也是计算斐波那契数最常见的了，也是最不省时间的，毕竟斐波那契数的增长很快。因为只要一个数大，那么下一个数会接近 2 倍的增长

#include <iostream>

using namespace std;

int fib(int n) {
    if (n == 2 || n == 1) { // 终止条件
        return 1;
    } else {
        return fib(n - 1) + fib(n - 2); // 前两项之和
    }
}

int main() {
    int number;
    cin >> number;
    cout << fib(number);
    return 0;
}

记忆优化法/递推

记忆优化法是递归的升级版本，因为递归要每个数二叉遍历，但是我目前只知道一个数优化

#include <cstdlib>
#include <iostream>
#include <string>

using namespace std;

long long a[200 + 10]; // 别忘了 kll (开 long long)
int n;

int main() {
    cin >> n;
    a[1] = 1; // 和递归终止条件一样
    a[2] = 1;
    for (int i = 3; i <= n + 1; i++) { // 开始循环
        a[i] = a[i - 1] + a[i - 2];    // 当前的数是前两项之和
    }
    cout << a[n]; // 输出当前的 n
    return 0;
}

高精度

高精度是 $YYDS$ 的，因为高精度他本身就有一个好的运算方式，还支持大数的运算，然而我们这个斐波那契数列其实只用到高精度加法（前两项之和）再配上记忆优化法的方式，不过我们要用 a[i] = 高精度函数(a[i-1],a[i-2]) 的方式

#include <bits/stdc++.h>

using namespace std;

string sum(string a, string b) { // 知周所众的高精度函数
    if (a.size() < b.size()) {
        swap(a, b);
    }
    for (int i = a.size() - 1, j = b.size() - 1; i >= 0; --i, --j) {
        a[i] = char(a[i] + (j >= 0 ? b[j] - '0' : 0));
        if (a[i] - '0' >= 10) { // 进位
            a[i] = char((a[i] - '0') % 10 + '0');
            if (i) {
                a[i - 1] += 1;
            } else {
                a = '1' + a;
            }
        }
    }
    return a;
}

string fib[203]; // 先开个表

int main() {
    fib[0] = "0";
    fib[1] = "1";
    for (int i = 2; i <= 200; ++i) {
        fib[i] = sum(fib[i - 1], fib[i - 2]); // 记忆优化法
    }
    int x;
    cin >> x;
    cout << fib[x] << endl; // 直线输出
    return 0;               // 完美结束
}