C++实现斐波那契数列

技术交流QQ群:1027579432，欢迎你的加入！

#include <iostream>

using namespace std;

// 递归方法和循环方法的对比
/*
递归方法代码实现比较简洁，但是性能不如循环方法，还会出现栈溢出的问题，优先采用递归的方法！
搜索路径的题目：一般使用回溯法，回溯法很适合使用递归方法的代码来实现！当要求不能使用递归实现的时候，考虑使用栈模拟递归的过程
求某个问题的最优解时，并且该问题可以拆分为多个子问题时：可以尝试使用动态规划的方法！在使用自上而下的递归思路去分析动态规划问题时，会发现子问题之间存在重叠
的更小的子问题。为了避免不必要的重复计算，使用自下而上的循环代码来实现，即把子问题的最优解先计算出来并用数组保存下来，然后基于子问题的解计算大问题的解。

特殊情况：在分解子问题的时候存在某个特殊的选择，采用这个特殊的选择将一定那个得到最优解，则此题目可能适用于贪心算法！
*/

class Solution{
public:
    // 递归方法实现
    int FibByRecursive(int n){
        if(n <= 0){
            return 0;
        }

        if(n == 1){
            return 1;
        }

        return FibByRecursive(n-1) + FibByRecursive(n-2);
    }
    // 循环方法实现
    int Fib(int n){
        if(n <= 0){
            return 0;
        }
        if(n == 1){
            return 1;
        }

        int first=0, second=1, third = 0;
        for(int i=2; i <= n; i++){
            third = first + second;
            second = first;
            third = second;
        }
        return third;
    }
};