斐波那契数列的c语言编程实现（递归和非递归）

   我们知道斐波那契数列是一组有规律的数列，后一个数都是前两个数字之和。0 1 1 2 3 5 8....
   下面是递归方法实现：

递归方法实现斐波那契
int Fib(int n)
{
	if (n == 0)
	{
		return 1;
	}
	else if (n == 1)
	{
		return 1;
	}
	else
		return Fib(n - 1) + Fib(n - 2);
 
}
int main()
{
	int n,ret;
	printf("请输入n:");
	scanf("%d", &n);
    ret = Fib(5);
	printf("%d\n", ret);
	system("pause");
	return 0
}
 

    递归方法虽然代码量少，容易理解，但是递归次数越大，程序的执行效率就越低。下面给出非递归方法实现的斐波那契数列代码实现。

int Fib(int n)
{
	int last2 = 0;//初始化的时候并不是斐波那契数列
	int last1 = 1;
	int fn = 0;
	for (int i = 2; i < n + 1; i++)
	{
		fn = last2 + last1;
		last1 = fn;
		last2 = last1;
	}
	return fn;

}
int main()
{
	int n, ret;
		printf("请输入n:");
		scanf("%d", &n);
	    ret = Fib(5);
		printf("%d\n", ret);
		system("pause");
		return 0;
}