关于非递归和递归分别实现求第n个斐波那契数

斐波那契数列：1,1,2,3,5,8,13,21,34......

前两个数为1，当n>=2时，后面的斐波那契数为前面两个斐波那契数之和。

非递归方法实现第N个斐波那契数

#include <stdio.h>
int main()
{
	int i = 0;
	int a = 1;
	int b = 1;
	int c = a + b;
	int n = 2;
	scanf("%d", &n);
	if (n > 2)//n<3则输出1，n>3进入循坏
	{
		for (i = 1; i <= n - 3; i++)//如第4个斐波那契数,只循坏1次.
		{
			a = b;		//a=1
			b = c;		//b=2
			c = a + b;	//c=3
		}
		printf("%d\n", c);//输出第4个斐波那契数3
	}
	else

		printf("%d\n", 1);//


	return 0;
}

递归方法实现第N个斐波那契数

#include <stdio.h>
int Fibonacci_number(int n)
{
	if (n == 1)
	{
		return  1;
	}
	if (n == 2)
	{
		return 1;
	}
	else
		return Fibonacci_number(n - 1) + Fibonacci_number(n - 2);
	
}
int main()
{
	int n = 0;
	scanf("%d",&n);
	printf("第%d个斐波那契数是%d\n", n, Fibonacci_number(n));
	return 0;
}

递归画图演示

假如scanf输入的n是4，进入Fibonacci_number(n)函数体内

  

调用函数完后，return返回值,先返回最后一趟递归函数Fibonacci_number(n - 1)的值是1， Fibonacci_number(n - 2)是1，1+1=2；再返回第二趟递归返回2、1，最终返回主函数值为3.

最终输出：第4个斐波那契数是3.