【C语言】斐波那契数列

文章目录

• 什么是斐波那契数列？
• 一、递归实现
• 二、非递归实现

---

什么是斐波那契数列？

1 1 2 3 5 8 13 21 34…,前两项为1，后面的值等于前两项值相加

一、递归实现

当n较大时 例如50，就会出现栈溢出的问题，这种时候需要我们用非递归来实现。

#include
int Fib(int n)
{
    //递归出口
	if (n < 3)
		return 1;
	else
	{
		return Fib(n - 1) + Fib(n - 2);
	}
}
int main()
{
	int n;
	scanf("%d", &n);
	int ret = Fib(n);
	printf("%d", ret);
	return 0;
}

二、非递归实现

#include
int Fib(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;
	scanf("%d", &n);
	int ret = Fib(n);
	printf("%d", ret);
	return 0;
}