C语言实现斐波那契数列（递归与非递归）

1.知识储备

• 斐波那契数列，又称黄金分割数列、费波那西数列、费波拿契数、费氏数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……在数学上，斐波那契数列定义为：F0=0，F1=1，Fn=Fn-1+Fn-2 n>=2，n∈N*。

2.递归(效率低，大量重复计算）

• n表示第n个斐波那契数。
• 当0<n<=2时，fib(n) = 1。
• 当n>2时，fib(n) = fib(n-1)+fib(n-2)。

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int fib(int n)
{
	if (n <= 2)
	{
		return 1;
	}
	else
	{
		return fib(n - 1) + fib(n - 2);
	}
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	printf("%d ", fib(n));
	return 0;
}

3.非递归

• 正向计算c = a+b,a= b,b =c,套入循环。
• 限制条件n > 2,每次循环n- -。

int fib(int n)
{
	int a = 1;
	int b = 1;
	int c = 1;

	while (n > 2)
	{
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	printf("%d ", fib(n));
	return 0;
}