3.斐波那契(Fibonacci)数列的定义为:它的第 1项和第 2项分别为0和1,以后各项为其前两项之和。若斐波那契数列中的第 n 项用 Fb(n)表示，试编写出计算 Fib(n)的递归算法和非递归算法,以及求出各自的时间和空间复杂度 long Fib(int n);//求斐波那契数列中第 n项的递归算法 long FibN(int n); //求斐波那契数列中第 n项的非递归算法

递归算法：

long Fib(int n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    return Fib(n - 1) + Fib(n - 2);
}

递归算法的时间复杂度为 O(2^n)，空间复杂度为 O(n)。

非递归算法：

long FibN(int n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    long f1 = 1, f2 = 1, f3 = 0;
    for (int i = 3; i <= n; i++) {
        f3 = f1 + f2;
        f1 = f2;
        f2 = f3;
    }
    return f3;
}

非递归算法的时间复杂度为 O(n)，空间复杂度为 O(1)。