第n个斐波那契数(C语言)

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

//思路:

//斐波那契数列指的是1,1,2,3,5,8,13,21……这样的一个数列

//第一个和第二个斐波那契数为1;

//从第三个斐波那契数开始,第n个斐波那契数等于第n-1个和第n-2个斐波那契数的和

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>

//非递归求第n个斐波那契数
void Fibonacci_non(int n){
	int f1 = 1;  //变量f1赋值为第一个斐波那契数值
	int f2 = 1;  //变量f2赋值为第二个斐波那契数值
	for (int i = 3; i <= n; ++i){  //从第三个斐波那契数开始求第n个斐波那契数
		f2 = f1 + f2;  //变量f2的值更新为f1和f2的和
		f1 = f2 - f1;  //变量f1的值更新为求和前f2的值
	}
	if (n == 1 || n == 2){  //若用户要第一个或第二个斐波那契的值
		printf("第%d个斐波那契数是%d.\n", n, f2);  //打印输出结果
	}
	else{
		printf("第%d个斐波那契数是%d.\n", n, f2);  //打印输出结果
	}
}

//递归求第n个斐波那契数函数
int Fibonacci(int n){
	if (n == 1 || n == 2){  //若n等于1或n等于2
		return 1;  //返回1
	}
	return Fibonacci(n - 1) + Fibonacci(n - 2);  //递归调用递归求第n个斐波那契数函数
}

//主函数
int main(){
	int n;  //变量n用以保存用户所要的斐波那契数
	int ret;  //变量ret用以接收递归调用的返回值
	printf("请输入您想要的n(即第n个斐波那契数):\n");  //提示用户输入信息
	scanf("%d", &n);  //用以保存用户所要的斐波那契数
	Fibonacci_non(n);  //调用非递归求第n个斐波那契数函数
	ret = Fibonacci(n);  //将递归求第n个斐波那契数函数的返回值赋给ret
	printf("第%d个斐波那契数是%d.\n", n, ret);  //打印输出结果
	system("pause");
	return 0;
}