斐波那契数列

题目描述
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39

解析
斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）

根据公式，最简单的实现方法就是通过递归的方式，但是递归会出现大量的重复。
优化方式，利用循环代替重复计算。

Java

/**
 * 递归
 * 运行时间：925ms
 * 占用内存：9424k
 */
public int fibonacci(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1 || n == 2){
        return 1;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

/**
 * 循环
 * 运行时间：19ms
 * 占用内存：9308k
 */
public int fibonacci2(int n) {
    int one = 0;
    int two = 1;
    int result = 0;
    if (n == 0) {
        return 0;
    } else if (n == 1){
        return 1;
    }
    for (int i = 2; i <= n; i++) {
        result = one + two;
        one = two;
        two = result;
    }
    return result;
}

Python

class Fibonacci:
    def fibonacci(self, n):
        if n <= 1:
            return n
        return self.fibonacci(n-1) + self.fibonacci(n-2)

    def fibonacci2(self, n):
        res = [0,1]
        while len(res) <= n:
            res.append(res[-1] + res[-2])
        return res[n]

if __name__ == '__main__':
    fibonacci = Fibonacci()
    print(fibonacci.fibonacci(10))
    print(fibonacci.fibonacci2(10))