采用递归

采用递归，$dfs(x)$ 的返回值是第 $x$ 项斐波那契数列的值，则输出 $dfs(n)$,递归的终止条件可以是当 $x=1$ 或 $x=2$ 时，返回 $1$。

#include <iostream>
using namespace std;

int dfs(int x) {
    if (x==1 || x==2) {
        return 1;
    }
    return dfs(x - 1) + dfs(x - 2);
}
int main() {
    int n;
    cin >> n;
    cout << dfs(n);
    return 0;
}