青蛙跳台阶 递归 C语言

青蛙跳台阶也是一道经典的递归题：一个青蛙，一次可以跳一级台阶，也可以一次跳两级台阶，问当跳n级台阶，有多少种跳法

到n等于4 的时候，我们发现并不是n=种类 那么简单，如果数学底子好，可以发现其实是n-1的种类加上n-2的种类。

接下来，我们通过图来分析：

假设n=3：假设我们站在第一节台阶上，往上跳有2种，也就是n=2的结果；而当我们站在第二节台阶上，就有一种跳法，即n=1时的结果，所以就是前两次的结果相加

我们用4再验证一下：假设我们站在第一层上，前面有三阶台阶，要3次；假设在第二级台阶，前面还有2层，即2次，所以是5种

假设是Jump函数：当n>=3时，Jump(n)=Jump(n-1)+Jump(n-2)

代码如下：

#include <stdio.h>

int Jump(int n)
{
  if (n == 1)
  {
    return 1;

  }
  else if (n == 2)
  {
    return 2;

  }
  else
  {
    return Jump(n - 1) + Jump(n - 2);
  }
}

int main()
{
  int n = 0;
  int a = 0;
  scanf("%d", &n);
  a = Jump(n);
  printf("%d", a);
  return 0;
  
}