更快、更少内存的双语解法

斐波那契数列是一道非常经典的递归题了，思路略，各种解法如下：
1.数组计算：

#include<iostream>
int main(){
    int n,f[31]={0,1};std::cin>>n;
    for(size_t i=2;i<n;i++)f[i]=f[i-1]+f[i-2];
    std::cout<<f[n];
    return 0;
}

f=[0,1]
for i in range(2,int(input())):
    f.append(f[i-1]+f[i-2])
print(f[-1])

2.递归算法：

#include<iostream>
int f(int n){
    if(n<=2)return 1;
    return f(n-1)+f(n-2);
}
int main(){
    int n;
    std::cin>>n;
    std::cout<<f(n);
    return 0;
}

def f(n):
    if n<=2:return 1
    return f(n-1)+f(n-2)
print(f(int(input())))

3.记忆化递归（推荐）：

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int fib(i){
        if(f[i]!=-1)return f[i];
        return f[i]=f[i-1]+f[i-2];
    }
    int x;cin>>x;
    vector<int>f(x+1,-1);
    f[0]=0;f[1]=1;
    cout<<fib(x);
    return 0;
}

或者：

#include<iostream>
#include<vector>
using namespace std;
vector<long long>f{1,1,1};
long long& fib(size_t i){
    if(i>=f.size())f.push_back(fib(i-2)+fib(i-1));
    return f.at(i);
}
int main(){
    int x;cin>>x;cout<<fib(x);
    return 0;
}

f=[1,1,1]
def fib(i):
    if i>=len(f):
        f.append(fib(i-2)+fib(i-1))
    return f[i]
print(fib(int(input())))