算法基础-斐波那契数列

斐波那契数列列
斐波那契数列列的是这样⼀一个数列列：1、1、2、3、5、8、13、21、34....，即第⼀项 f(1) = 1,第⼆二项
f(2) = 1.....,第 n 项⽬目为 f(n) = f(n-1) + f(n-2)。求第 n 项的值是多少。

1、第⼀一递归函数功能
假设 f(n) 的功能是求第 n 项的值，代码如下：

int f(int n){
}

2、找出递归结束的条件
显然，当 n = 1 或者 n = 2 ,我们可以轻易易着知道结果 f(1) = f(2) = n。所以递归结束条件可以为 n <= 2。
代码如下：

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

第三要素：找出函数的等价关系式
题⽬已经把等价关系式给我们了了，所以我们很容易就能够知道 f(n) = f(n-1) + f(n-2)。等价关系
式是最难找的一个，而这个题目却把关系式给我们了
所以最终代码如下

int f(int n){
// 1.先写递归结束条件
if(n <= 2){
return n;
}
// 2.接着写等价关系式
return f(n-1) + f(n - 2);
}