递归算法之-斐波那契数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称“兔子数列”。

斐波那契数列是指这样一个数列：1，1，2，3，5，8，13，21，34，55，89……这个数列从第3项开始 ，每一项都等于前两项之和。

现在给出一个问题，第 n 项目为 f(n) = f(n-1) + f(n-2)。求第 n 项的值是多少。

按照前面的文章，一步一步来

1.明确这个函数是干什么的

// 输入一个整数n，求出第n项的斐波那契数
int f(int n){
	
}

2.寻找递归结束条件

当n=1或n=2时，结果显而易见。都为1

int f(int n){
	if (n <= 2) return 1;
}

3.找出函数等价关系式

将f(n)缩小范围，f(n-1)，f(n)和f(n-1)等关系为，f(n) = f(n - 1) + f(n -2)

// 输入一个整数n，求出第n项的值
int f(int n){
	if (n <= 2) return 1;
	return f(n - 1) + f(n -2);
}