【408】斐波那契数列

非递归使用循环计算，通过prev、current、temp来不断计算第n项
即
int temp=current;【下一步变为前一项】
current+=prev
prev=temp

#include <iostream>
#include <vector>

//递归解法的时间复杂度是指数级的，为 O(2^n)。
//非递归解法的时间复杂度是线性的，为 O(n)

using namespace std;

// 递归解法
int fibonacciRecursive(int n) {
    if (n <= 1)
        return n;
    return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

// 非递归解法
int fibonacciNonRecursive(int n) {
    if (n <= 1)
        return n;

    int prev = 0;
    int current = 1;
    for (int i = 2; i <= n; ++i) {
        int temp = current;
        current += prev;
        prev = temp;
    }
    return current;
}

int main() {
    int n = 10; // 示例输入
    cout << "递归解法：" << fibonacciRecursive(n) << endl;
    cout << "非递归解法：" << fibonacciNonRecursive(n) << endl;
    return 0;
}