c++递归问题求解：2790: 菲波那契数列

Question

题目描述
菲波那契数列是指这样的数列：数列的第一个和第二个数都为1，接下来的每个数都等于前面2个数字之和。
给出一个正整数a，要求菲波那契数列中第a个数对1000取模的结果是多少。
输入
第1行是数据的组数n(n<=100000)，后面跟着n行输入。每组测试数据占1行，包括一个正整数a(1<=a<=1000000)。
输出
n行，每行输出对应一个输入。输出应是一个正整数，为菲波那契数列中第a个数对1000取模得到的结果。
样例
输入
4
5
2
19
1
输出
5
1
181
1

Answer 1

不能用递归求，否则递归次数太多会导致栈溢出

#include <iostream>

using namespace std;

int fibonacci(int a)
{
    if (a == 1 || a == 2)
        return 1;
    int f1 = 1, f2 = 1;
    for (int i = 3; i <= a; i++)
    {
        int f = (f1 + f2) % 1000;
        f1 = f2;
        f2 = f;
    }
    return f2;
}

int main()
{
    int n, a;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a;
        cout << fibonacci(a) << '\n';
    }
    return 0;
}