斐波那契数列·题解

#include<iostream>
using namespace std;
int arr[20] = {1,1};
int f(int n){
    if(n<3){
        return 1;
    }else{
        return f(n-1)+f(n-2);
    }
}
int main(){
    int n;
    cin>>n;
    cout<<f(n);
    return 0;
}

思路：
这题我们可以使用递归算法。
首先我们要弄明白递归式，斐波那契数列的规律：
一个数 = 前两个数的和
这道题最大的任务个数（功能被调用的次数）为一个二叉树的形式，从$2^0$一直加到$2^{20}$,所以我们不用记忆化
废话少说，递归式显然为：

$$F(n)= \begin{cases} 0, & n=0 \\ 1, & n=1 \\ F(n-1)+F(n-2), & n\ge 2 \end{cases}$$

而0不用管，我们只用写另外两个分支就行
最终，递归主体就能根据递归式改编为代码：

int f(int n){
    if(n<3){
        return 1;
    }else{
        return f(n-1)+f(n-2);
    }
}