递归

当前 = 前一个 + 前两个，递归极其容易超时

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

迭代

递归容易超时，那是递归在计算的时候，计算过很多次已经计算过的结果，可以保存下来

迭代的时候，只关注当前的数的前一个和前两个，每次用变量临时纪录起来，那么只需相加即可，而不是像递归那样重复计算

public class Solution {
    public int Fibonacci(int n) {
        if(n <= 1){
            return n;
        }
        int pre2 = 0, pre1 = 1;
        for (int i = 2; i <= n; i++){
            int cur = pre2 + pre1;
            pre2 = pre1;
            pre1 = cur;
        }
        return pre1;
    }
}