斐波那契数列指的是这样一个数列：0、1、1、2、3、5、8、13、21、34......，仔细观察这个数列的规律可得出，第0项和第一项分别是他们本身，从第二项开始每一项等于前两项相加之和，下面我们根据这个规律来实现以下求斐波那契数列的第N项
斐波那契数列的实现方法有很多种，下面我们用两种方式实现一下(以下代码都是C语言实现)
一.递归算法实现
int Fibo1(int n)
{
if (n < 2) {
return n;
}
return Fibo1(n - 1) + Fibo1(n - 2);
}
二.for循环实现
int Fibo2(int n)
{
if (n < 2) {
return n;
}
int sum;
int first = 0;
int second = 1;
for (int i = 0; i < n - 1; i++) {
sum = first + second;
first = second;
second = sum;
}
return second;
}
以上两种实现方式对比，第一种的时间复杂度为O(2^n)，第二种的时间复杂度为O(n)，项目中为了节省运行时间和空间，我们尽量采用复杂度低的算法来实现功能，所以比较推荐第二种实现方式。
