recursion_frog.cpp

#include <iostream>
#include <array>
#include <algorithm>
using namespace std;

// 先定义一个函数，明确这个函数的功能，由于递归的特点是问题和子问题都会调用函数自身，所以这个函数的功能一旦确定了， 之后只要找寻问题与子问题的递归关系即可
// 接下来寻找问题与子问题间的关系（即递推公式），这样由于问题与子问题具有相同解决思路，只要子问题调用步骤 1 定义好的函数，问题即可解决。所谓的关系最好能用一个公式表示出来，比如 f(n) = n * f(n-) 这样，如果暂时无法得出明确的公式，用伪代码表示也是可以的, 发现递推关系后，要寻找最终不可再分解的子问题的解，即（临界条件），确保子问题不会无限分解下去。由于第一步我们已经定义了这个函数的功能，所以当问题拆分成子问题时，子问题可以调用步骤 1 定义的函数，符合递归的条件（函数里调用自身）
// 将第二步的递推公式用代码表示出来补充到步骤 1 定义的函数中
// 最后也是很关键的一步，根据问题与子问题的关系，推导出时间复杂度,如果发现递归时间复杂度不可接受，则需转换思路对其进行改造，看下是否有更靠谱的解法

// 一只青蛙可以一次跳 1 级台阶或一次跳 2 级台阶,例如:
// 跳上第 1 级台阶只有一种跳法：直接跳 1 级即可。跳上第 2 级台阶
// 有两种跳法：每次跳 1 级，跳两次；或者一次跳 2 级。
// 问要跳上第 n 级台阶有多少种跳法？

// f(n) = f(n-1) + f(n-2)
int f(int n)
{
    if (n == 1) return 1;
    if (n == 2) return 2;
    return f(n-1) + f(n-2);
}
int g(int n)
{
    if (n == 1) return 1;
    if (n == 2) return 2;
    int prepre = 1;
    int pre = 2;
    int res = 3;
    for (int i = 3; i < n; i++) {
        prepre = pre;
        pre = res;
        res = prepre + pre;
    }
    return res;
}
int main()
{
    // bad approach 
    cout << f(6) << endl;
    // good approach
    cout << g(6) << endl;
    return 0;   
}