/递归和非递归分别实现求第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等于2return 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个斐波那契数函数的返回值赋给retprintf("第%d个斐波那契数是%d.\n", n, ret); //打印输出结果system("pause");return 0;}
