C++ 经典斐波那契函数

经典的斐波那契数列是一个递归定义的序列，其中每个数字都是前两个数字之和。在C++中，你可以通过递归函数来实现这个函数，但是由于递归可能导致大量的重复计算，效率不高。下面是一个简单的递归实现：

#include <iostream>

// 递归版本的斐波那契函数
int fibonacciRecursion(int n) {
    if (n <= 1)
        return n;
    else
        return fibonacciRecursion(n - 1) + fibonacciRecursion(n - 2);
}

int main() {
    int num;
    std::cout << "请输入一个非负整数: ";
    std::cin >> num;

    if (num < 0)
        std::cerr << "错误! 斐波那契数只对非负整数定义." << std::endl;
    else
        std::cout << "斐波那契数列第" << num << "项是: " << fibonacciRecursion(num) << std::endl;

    return 0;
}

不过，对于较大的n值，递归版本可能会非常慢。为了提高性能，你可以使用动态规划或迭代的方式来避免重复计算：

// 动态规划版本（记忆化搜索）
int fibonacciMemoization(int n, std::vector<int>& memo) {
    if (n <= 1 || memo[n] != -1)
        return memo[n];

    memo[n] = fibonacciMemoization(n - 1, memo) + fibonacciMemoization(n - 2, memo);
    return memo[n];
}

int main() {
    int num;
    std::cout << "请输入一个非负整数: ";
    std::cin >> num;

    std::vector<int> memo(num + 1, -1); // 初始化一个足够大的数组存储已计算的斐波那契数值

    if (num < 0)
        std::cerr << "错误! 斐波那契数只对非负整数定义." << std::endl;
    else
        std::cout << "斐波那契数列第" << num << "项是: " << fibonacciMemoization(num, memo) << std::endl;

    return 0;
}

在这个迭代版本中，我们利用一个`memo`数组来存储已经计算过的斐波那契数值，提高了效率。