c语言递归 青蛙跳台阶

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

当n=1，有1种方法。
当n=2，有2种方法。
当n=3，有3种方法。
当n=4，有5种方法。

假设：青蛙跳到n阶，有 f(n) 种跳法。
如果只看最后一步，那么有两种跳法：

1. 从n-2层跳到n层。
2. 从n-1层跳到n层。

那么可以得出：当n>2时，f(n)=f(n-1)+f(n-2)，

可以这样定义函数：

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

但是当同时递归n-1和n-2时，递归函数效率低下。
更推荐用迭代的方法：

int Jump(int n)
{
	if (n > 2)
	{
		int a = 1;
		int b = 2;
		int c = 0;
		for (int i = 3; i <= n; i++)
		{
			c = a + b;
			a = b;
			b = c;
		}
		return c;
	}
	else
	{
		return n;
	}
}

举一反三

如果青蛙可以同时跳3阶台阶，那么青蛙跳上一个n级的台阶总共有多少种跳法？
当n=1，有1种方法。
当n=2，有2种方法。
当n=3，有3种方法。
当n=4，有5种方法。
当n=5，有10种方法。

只看最后一步，有三种方法可以跳上f(n)

1. 从f(n-3)层。
2. 从f(n-2)层。
3. 从f(n-1)层。

同理，n>3时，f(n)=f(n-1)+f(n-2)+f(n-3)。