#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屿良，發(fā)現在計算運行
一開始long長整型都不夠用了圈澈，顯示出來是負的，顯示不完整
斐波那契顯示不完整.jpg
尘惧，
然后用了無符號unsigned long長整型
斐波那契.jpg
剛才運行花了2分鐘康栈，經過大佬指點
問題在執(zhí)行過程中的:
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];//返回上一次函數
}
