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

题目描述
菲波那契数列是指这样的数列：数列的第一个和第二个数都为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

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

#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;
}

#include <iostream>

using namespace std;

int main()
{
    int n;
    int a[200];          //输入的第N个数字
    int f[1000001];    //将1000000个斐波那契数取1000的模都求出来
    f[1]=1;
    f[2]=1;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    for(int i=3;i<1000001;i++)
    {
        f[i]=(f[i-1]+f[i-2])%1000;           //高精度取模
    }
    for(int i=0;i<n;i++)
    {
        cout<<f[a[i]]<<endl;        //将输入的数字a[i]当成脚标用于f[]中，求出输入数字的斐波那契数取模的结果
    }
    return 0;
}

#include<iostream>
using namespace std;
int fib(int x)
{
    if(x==1||x==2)return 1;
    else return (fib(x-1)+fib(x-2))%1000;
    
}
int main()
{
    int n,x;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        cout<<fib(x)<<endl;
    }

    return 0;
} 

以上是递归写法，不过递归的话容易栈溢出，可以参考楼上的递推。