c++斐波那契数列递归，超时

Question

##计算斐波那契数列的函数
#题目要求用递归方法，n取0--90，所有运算在30秒内完成
我写的代码运算花费的时间很长，大概在接近50的时候就开始超时了，如何优化一下？

#include <iostream>

using namespace std;

long long fibonacci[91];  //储存已经计算的数列

long long fibonacci_calculate(int n) {
    if (n == 0) { fibonacci[0] = 0; return 0; }
    if (n == 1) { fibonacci[1] = 1; return 1; }
    if (n == 2) { fibonacci[2] = 1; return 1; }
    else { 
        fibonacci[n] = fibonacci_calculate(n - 1)+fibonacci_calculate(n - 2);
        return fibonacci[n];
    }
}
//斐波那契数列的递归函数

int main() {
    int ops=0;  //储存到几的斐波那契数列
    int n;
    while (1) {
    
            cin >> n;  //当前要的项数
            if (cin.fail()) {  //输入的是char型，fail()函数会返回true，进入if
                cin.clear();
                cin.ignore();
                cout << "WRONG" << endl;
            }

            else {   //输入合法
                if (n <= ops) { cout << fibonacci[n] << endl; }  //n<ops直接提取
                else {
                    cout << fibonacci_calculate(n) << endl;
                    ops = n;
                }
                //n>ops，计算斐波那契数列
            }    
    }
    return 0;
}

Answer 1

##问题在于迭代时 fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
这一语句块会使得函数递归分支，加倍递归运算
应只递归一次，把结果储存在数组中，每一次加数组中的数
#改正后代码

#include <iostream>

using namespace std;

long long fibonacci[91] = {0,1};  //初始化斐波那契数组

long long fibonacci_calculate(int n) {
    if (n == 0) {  return 0; }
    if (n == 1) {  return 1; }
    else { 
        {
            fibonacci[n] = fibonacci_calculate(n - 1) + fibonacci[n - 2];//这里进行优化，用数组中的数，不用递归两次
        }
        return fibonacci[n];
    }
}
//斐波那契数列的递归函数

int main() {
    int ops=0;  //储存到几的斐波那契数列
    int n;
    while (1) {
    
            cin >> n;  //当前要的项数
            if (cin.fail()) {  //输入的是char型，fail()函数会返回true，进入if
                cin.clear();
                cin.ignore();
                cout << "WRONG" << endl;
            }
            //如何判断小于90？

            else {   //输入合法
                if (n <= ops) { cout << fibonacci[n] << endl; }  //n<ops直接提取
                else {
                    cout << fibonacci_calculate(n) << endl;
                    ops = n;
                }
                //n>ops，计算斐波那契数列
            }    
    }
    return 0;
}