斐波那契數列的兩種簡單實作

近期一次面試，提到了斐波那契數列的實作，算法還是比較簡單的，用了兩種方法實作（兩種方式寫到了一個程式中），代碼如下：

#include "stdio.h"
#include "stdlib.h"

int fibonacci(int step)
{
	if (step == 0)
		return 0;
	if (step == 1)
		return 1;
	return fibonacci(step-1)+fibonacci(step-2);
}

int main()
{
	int n = 0;
	printf("Please Input the interger:\n");
	scanf("%d", &n);
	
	//使用遞歸方式
	int value = fibonacci(n);
	printf("Using Recursive, Fibonacci %d is %d\n", n, value);
	
	//使用正常數組方式
	value =0;
	int a[2]={0};
	a[0]=0;
	a[1] =1;
	if (n ==0)
		value=0;
	else if (n == 1)
		value = 1;
	else
	{
		for(int i =2; i <= n; i++)
		{
			value = a[1]+a[0];
			a[0]=a[1];
			a[1]=value;
		}
	}

	printf("Using Array, Fibonacci %d is %d\n", n, value);
	
	return 0;
}
           

面試過程中讨論如下：

遞歸和數組方式，那個更好？簡單說，遞歸方式的時間複雜度要高，算法可讀性一般，數組方式時間複雜度O(n)，易了解。在資料n很大的情況下，遞歸方式的性能很差

兩種算法各有千秋。

如何設計測試用例對代碼進行測試？資料0,1,2必須測試，另随機找幾個整數。取n較大時檢視算法占用的時間和資源。算法中使用了int做為存貯數值的結果，n較大時可能會造成溢出。

大緻就是這些了，很長時間沒有關注過基礎算法，面試中提到了有沒有更優化的算法，沒有回答出來，發揮一般。

ps：還不知道什麼是大名鼎鼎的斐波那契數列嗎？如果是，那就搜尋一下吧，有所耳聞，那就深度搜尋一下其在各個方面的應用，很有意思的。

ps：增加時間跟蹤函數發現，n在大于40以後，遞歸算法簡直無法忍受，大概是函數調用開銷實在是太大了。

另如果用int儲存結果值，那麼n=47時就溢出了，需要使用long但是到了一定的數量也會溢出。