用递归实现打印第n个Fibonacci数列

#include<stdio.h>

int main()
{
    unsigned long F[100]={0,1},fn;
    int n;
    unsigned long recursion(int x,unsigned long F[]);
    
    printf("请输入一个整数n（0<x<100）,输出斐波那契数列的第n数！\n");
    scanf("%d",&n);
    fn=recursion(n,F);
    printf("第%d数Fn=%lu",n,fn);
}
unsigned long recursion(int x,unsigned long F[])
{
    if(x>0+2)
    {
            F[x]=recursion(x-1,F)+recursion(x-2,F);
            //n>2时，Fn=F(n-1)+F(n-2) 
    }
    else if(x=2)
    {
        F[x]=F[x-1]+F[x-2];
    }
    return F[x];//返回上一次函数 
}

计算第50个的时候用了2分多钟。我还以为哪里出错了没运行呢，看了一下CPU，发现在计算运行

一开始long长整型都不够用了，显示出来是负的，显示不完整

斐波那契显示不完整.jpg

，
然后用了无符号unsigned long长整型

斐波那契.jpg

刚才运行花了2分钟，经过大佬指点

问题在执行过程中的:

F[x]=recursion(x-1,F)+recursion(x-2,F);

时进行了两次函数递归，每一次递归就要运行2次。
就像 1乘1乘1乘1乘1乘1乘1...... 被我两次计算，变成了 2乘2乘2乘2乘2乘2......
你们说计算哪个快
，计算次数很多导致运行缓慢

在进行recursion(x-1,F)递归时已经计算出了
F【x-1】=F【x-2】+F【x-3】
F【x-2】=F【x-3】+F【x-4】
...以此类推，递归回去，直到不满足X>2的条件

在此可以看出其实F【x-2】是计算过了一遍了的

所以只要把F【x-2】调用出来就行，
免去的再次计算步骤，

F[x]=recursion(x-1,F)+F[x-2];

然后一试，MD真的快了好多好多，同样是输出第50个数只花了不到1秒的时间

#include<stdio.h>

int main()
{
    unsigned long F[100]={0,1},fn;
    int n;
    unsigned long recursion(int x,unsigned long F[]);
    
    printf("请输入一个整数n（0<x<100）,输出斐波那契数列的第n数！\n");
    scanf("%d",&n);
    fn=recursion(n,F);
    printf("第%d数Fn=%lu",n,fn);
}
unsigned long recursion(int x,unsigned long F[])
{
    if(x>0+2)
    {
            F[x]=recursion(x-1,F)+F[x-2];
            //n>2时，Fn=F(n-1)+F(n-2) 
    }
    else if(x=2)
    {
        F[x]=F[x-1]+F[x-2];
    }
    return F[x];//返回上一次函数 
}