509. 斐波那契数🔖递归

function fib(n: number): number {
  if (n <= 1) return n
  return fib(n - 1) + fib(n - 2)
}

class Solution {
    // TODO: for循环实现
    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;
            first = second;
            second = sum;
        }
        return second;
    }
//    // TODO: 递归实现O(2^n)
//    public int fib1(int n) {
//        if (n <= 1) return n;
//        return fib1(n - 1) + fib1(n - 2);
//    }
//    // TODO: 首尾实现
//    public int fib3(int n) {
//        if (n <= 1) return n;
//        int first = 0;
//        int second = 1;
//        while (n-- > 1) {
//            second += first;
//            first = second - first;
//        }
//        return second;
//    }
}

// 递归：O(2^n)
public static int fib1(int n) {
    if (n <= 1) return n;
    return fib1(n - 1) + fib1(n - 2);
}

// for循环：O(n)
public static int fib2(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;
        first = second;
        second = sum;
    }
    return second;
}
// 首尾法
public static int fib3(int n) {
    if (n <= 1) return n;

    int first = 0;
    int second = 1;
    while (n-- > 1) {
        second += first;
        first = second - first;
    }
    return second;
}
// 特征方程解法：O（1）
public static int fib4(int n) {
    double c = Math.sqrt(5);
    return (int) (Math.pow((1+c) / 2, n) - Math.pow((1-c) / 2, c));
}