斐波那契数列指的是这样一个数列：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)，项目中为了节省运行时间和空间，我们尽量采用复杂度低的算法来实现功能，所以比较推荐第二种实现方式。