用C 语言实现斐波那契数列

斐波那契数列（Fibonacci sequence），又称“黄金分割”数列，比如这样一个数列：1，1，2，3，5，8，13，21，34，55，89... ...数列从第3项开始，每一项都等于前两项之和。在C语言中，我们可以用多种方式来实现斐波那契数列。本文针对以下三种方式来体现每种方法的效率：1）递归，2）非递归，3）数组。

1. 递归。该递归属于多分支递归，会造成栈溢出。

//递归
	#include<stdio.h>

	int Fib(int n)
	{
		if(n==1||n==2)//数列前两项
		{
		return 1;
		 }
		else//从第三项开始
		{
		return Fib(n - 1) + Fib(n - 2);
		}
		return 0;
	}
	int main()
	{
		int n = 0;
		scanf("%d", &n);//输入一个数
		int ret = Fib(n);//计算斐波那契数列
		printf("%dn", ret);//打印结果
		return 0;
	}

2）非递归。非递归较递归效率更高，避免了重复计算的时间和空间。

//非递归
int main() 
{
	int n = 0;
	printf("请输入一个整数：");
	scanf("%d", &n);
	if (n == 1||n==2) {
		return 1;
	}else {
		int f1 = 1;
		int f2 = 1;
		int f3 = -1;
		for (int i = 3; i <= n; i++) {
			f3 = f1 + f2;
			f1 = f2;
			f2 = f3;
		}
		printf("该整数的Fib数列为%d", f3);
	}

	return 0;
}

3）数组。

	//数组法	
	#include<stdio.h>

	int Fib(int n)
	{
		int i;
		int arr[100] = {0,1,1};
		for (i = 2; i <= n; i++)//从第一项开始
		{
			arr[i] = arr[i - 1] + arr[i - 2];    
		}
		return arr[n];
	}
	int main()
	{
		int n;
		scanf("%d", &n);
		printf("%d", Fib(n));
		return 0;
	}