第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;
}