面试题9：斐波那契数列

题目一：写一个函数，输入n，求斐波那契（Fibonacci）数列的第n项。斐波那契数列的定义如下：（斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。）
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

1. 递归（效率很低的解法）

public int Fib(int n)
{
    if (n == 0)
        return 0;
    if (n == 1)
        return 1;

    return Fib(n - 1) + Fib(n - 2);
}

2. 循环

public int Fib(int n)
{
    if (n < 2)
        return n;
    var num1 = 0;
    var num2 = 1;
    var temp = 0;
    for (var i = 2; i <= n; i++)
    {
        temp = (num1+num2) % 1000000007;
        num1 = num2;
        num2 = temp;
    }
    return temp;
}

用不同的方法求解斐波那契数列的时间效率大不相同。第一种基于递归的解法虽然直观但时间效率很低，在实际软件开发中不会用这种方法，也不可能得到面试官的青睐。第二种方法把递归的算法用循环实现，极大地提高了时间效率。