509. 斐波那契数

leetCode地址
用Java写的
递归

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

非递归

class Solution {
    public int fib(int N) {
        if(N<=1) return N;
        int first = 0;
        int second = 1;
        for(int i = 0;i < N-1; i ++){
            int sum = first + second;
            second += first;
            first = second - first;

        }
        return second;
    }
}

class Solution {
    public int fib(int N) {
        if(N<=1) return N;
        int first = 0;
        int second = 1;
        while (N --> 1){
            second += first;
            first = second - first;
        }
        return second;
    }
}