C语言用递归和迭代实现斐波那契数列

• 写在前面
• Fibonacci数列
• 用递归来实现
• 用迭代来实现
• 写在最后

今天在作业题中看见了斐波那契数列(Fibonacci数列)，相信大家或多或少都听过，具体如上图，实际上用C语言打印出来后也蛮有意思的，故而想在这里和大家一起分享！

作者：Shining-point
作者的博客主页：Shining-point的博客
如果觉得博主的博客写的不错或者有所收获的话，希望大家多多点赞 评论收藏，你们的支持是我的最大动力，不驰于空想,不骛于虚声，我们一起加油！！！

在开始编写我们的程序之前，我们先理理思路

既然知道了具体表达式，开始动手吧

//递归
#include 

int Fibonacci(int n)
{
	if (n <= 2)
	{
		return 1; //n<=2时的情况
	}
	else
	{
		return Fibonacci(n - 1) + Fibonacci(n - 2); //n>2时的情况
	}
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = Fibonacci(n);
	printf("%d", ret);
	return 0;
}

如果事情能轻松结束自然是好，但同时我们也注意到这段代码的效率之差，具体如何差呢，用一段代码来告诉你

#include 

int count = 0;//创建全局变量count用来计数

int Fibonacci(int n)
{
	if (n == 3)
	{
		count++;//每当计算第三个数时，count++
	}

	if (n <= 2)
	{
		return 1; //n<=2时的情况
	}

	else
	{
		return Fibonacci(n - 1) + Fibonacci(n - 2); //n>2时的情况
	}
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = Fibonacci(n);
	printf("%dn", ret);
	printf("第三个数计算了%d遍n", count);
	return 0;
}

由此可见用递归来计算第n个Fibonacci数列充斥着大量的重复计算，影响了效率和准确性，那么在这里我们可以用效率更高的迭代

//迭代
#include 

int Fibonacci(int n)
{
	int a = 1;
	int b = 1;
	int c = 1;
	while (n >= 3)
	{
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = Fibonacci(n);
	printf("第%d个Fibonacci数列为%dn",n, ret);
	return 0;
}

至此可见，计算第n个Fibonacci数列时，迭代的效率和准确性都优于递归，我们是不是可以理解在面对一个问题时要保持寻求最优解的态度