【C语言】递归经典问题——青蛙跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

设函数jump(n)表示青蛙跳上n级台阶的跳法种数。

当n=1时，只有1种跳法。

当n=2时，可以一次跳1级台阶，跳两次；也可以一次跳2级台阶，跳一次。所以一共有2种跳法。

当n>3时，如果先跳1级台阶，还剩n-1级台阶，有jump(n-1)种跳法；如果先跳2级台阶，还剩n-2级台阶，有jump(n-2)种跳法。所以一共有jump(n-1)+jump(n-2)种跳法。

#include 

int jump(int n)
{
    if (n <= 2)
        return n;
    else
        return jump(n - 1) + jump(n - 2);
}

int main()
{
    int n = 0;
    scanf("%d", &n);
    int ret = jump(n);
    printf("%dn", ret);
    return 0;
}

可以看出青蛙跳台阶就是斐波那契数列的应用。