小青蛙跳台阶（递归经典面试题）C#

https://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4

题目来源于牛客网上的一道经典面试题

对于这道题目，我们先来从浅入深的找出解题规律

我们先假设number = 1，那么就只有一种跳法

假设number = 2,  那么就是两种跳法（先跳一阶再跳一阶，或者直接跳两阶）

假设number = 3，那么有三种跳法：

                             先跳一阶，再跳两阶，或者先跳一阶再跳一阶，再跳一阶（两种，n-2）

                              先跳两阶，再跳一阶 （一种，n - 1）

假设number = 4，那么有5种跳法：

                                先跳一阶，再跳...（n - 2）

                                先跳两阶，再跳...（n - 1）

大家是不是发现，从第三阶开始，就有点类似于斐波那契数了，当台阶超过2的时候，大概无非就两种 跳法，第一是先跳一阶剩下N-2，或者先跳两阶剩下N-1

那么我们使用递归的方法就很好实现这段代码了

#include 
int Fand(int n)
{
	if (n == 1)
		return 1;
	if (n == 2)
		return 2;
	return Fand(n - 1) + Fand(n - 2);

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

	int ret = Fand(n);

	printf("%d", ret);
	return 0;
}