求助，关于记忆递归求pell数列

447908543

#include <stdio.h>

#define MAX 1000000

#define K 32767

unsigned long long int array[MAX+1];// 记忆递归

unsigned long long int f(int num)
{
        if(array[num]!=0)//归时调用记忆
        return array[num];
        else if(num==1)
        return 1;
        else if(num==2)
        return 2;
        return array[num]=((2*f(num-1)%K)+(f(num-2)%K));//递时生成记忆
}
int main(void)
{
        int n,num;
        scanf("%d",&n);
        while(n--)
        {
                scanf("%d",&num);
                printf("%lld\n",f(num));
        }
        return 0;
}
代码如上，在num规模较小时答案正确，但是测试输入大概num>100后，输出结果有误
比如我输入100返回27500，输入1000，10000结果都是27500
我输入101返回43933，输入1001，10001结果返回都是43933
规模更大的num程序无法返回结果
接触递归不久，希望大神们不吝赐教，万分感谢！！！

beijudezixuan

递归的实现是通过栈来进行的，程序栈空间是有限的。这样的代码在时间消耗和空间消耗上都是随num的增加呈现指数型的增长(2的x次方的增长速度，可以试想一下num较大时的递归层数)，所以当num过大在时间和空间上都是无法被满足的。
要了解具体的知识的话，楼主可以去搜索一下递归与栈的关系哦0.0