题解 | #斐波那契数列#

思路
递归：利用斐波那契数列的特征第n项的值是第n-1项与第n-2项的和，计算第n项的值，那么就递归获取第n-1项与第n-2项，然后返回它们的和。

变量法：同样是利用斐波那契数列的特征，记变量：first，second，result，那么再引入一个辅助变量temp就可以实现往后挪动，直到计算出最终result。

结果

1. 递归法
   运行时间：339ms
   占用内存：10640KB
2. 变量法
   运行时间：18ms
   占用内存：10748KB

代码

1. 递归法

   public int Fibonacci(int n) {
        if (n <= 1){
            return n;
        }
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }

2. 变量法

   public int Fibonacci(int n) {
        if (n <= 1){
            return n;
        }
        int first = 0;
        int second = 1;
        int result = first + second;
   
        for (int i = 3; i <= n; i++) {
            int tempVal = result;
            result = second + result;
            first = second;
            second = tempVal;
        }
        return result;
    }