函數遞歸求斐波那契數列

//函數遞歸求斐波那契數列
//編寫程式，求數列1,1,2,3,5,8,13,21,……
//思路:
//第一步:找出表示數列第N項的遞歸公式:F(N)=F(N-1)+F(N-2)
//第二步:遞歸的結束條件，當N=1或N=2時，F(N)=1;

long int Fib(int n)
{
	if (n <= 2)
		return 1;
	else
		return Fib(n - 1) + Fib(n - 2); 
	//拿n=3帶入一下，第一個傳回值為1 第二個傳回值1 是以第三項是2
}
int main()
{
	int n;
	scanf("%d", &n);
	printf("第%d項的斐波那契數是:%ld\n", n, Fib(n));
	return 0;
}
//總結：
//編寫遞歸的 要點
//1）：找到正确的遞歸算法，這是編寫遞歸程式的基礎
//2) ：确定遞歸算法的結束條件，這是決定遞歸程式能否正常結束的關鍵

//數值問題，可以表達為數學公式，從數學公式推導出問題的遞歸定義（也就是算法的具體步驟），然後
//确定問題的邊界條件，進而确定遞歸的算法和遞歸結束條件