青蛙跳台阶JAVA
一只青蛙一次可以跳上一层台阶，也可以跳上两层，求该青蛙跳上n层的台阶总共有多少种跳法(先后次序不同算不同的结果)。
思考：可以看出，每次青蛙出脚都会有两种可能,一步或者两步，再次出脚也是两种可能，一步或者两步，每次出脚就是一步或者两步，那么，何时青蛙不能出脚了，很显然，是台阶走完了，所以，青蛙跳台阶每种跳法都是1和2的各种组合；先来看看层数和方法数之间规律吧！(这里用到了类似信息论中码树的方法来分析，没听过也没关系，看图就行)
递归法求解
递归
在用递归之前，先来谈谈对递归的认识吧，所谓递归，可以把它分解为递+归两个过程，现在假设小明坐在教室最后一排，他的衣服放在第一排，于是他给倒数第二排的人说帮他拿一下衣服，倒数第二排的人给倒数第三排的人说给他拿一下衣服…直到第二排的人给第一排的人说帮他拿一下衣服 ，这便是递；第一排的人将衣服递给第二排的人，第二排的人把衣服递给第三排的人…倒数第二排的人把衣服给倒数第一排的人。好了目的达到了，最后一排的人获得了他的衣服这便是归。最后一排的人只用去告诉他前面的人帮他取一下衣服，而更前面的人消息怎么传，最后一排的人就不用管了，就假设消息已经送到了。但是能保证最后一排的人能拿到衣服，就必须消息到达第一排的人时，第一排的人能够把衣服递给第二排的人。(当然，你可能会说，最后一排的人直接去第一排把衣服一取不就行了，哈哈，这里我们只是为了解决问题举出这个例子，不用去在意这些细节。)
这时会发现，其实每个人重复的动作都是一样的，都是把消息传达给坐在他前面的人，然后在衣服传达到他那里时，把衣服传给坐在他后面的人，那么问题不就简单了，把倒数第二排以前的人看做一个整体，倒数第一排的人只是让倒数第二排的人帮他拿一下衣服，这样一次递，最后将衣服归回来，OVER。
所以，这时我们可以定义一个方法，就是向前面的人发送帮忙取衣服的请求，当这排只有两个人时，那么前面的人就把衣服给后一个人，如果一排有十个人时，就只用向第九个人发送帮忙取衣服的请求，至于第九个人怎么取，其实也是用的相同的方法。
这就是递归，下面就用青蛙跳台阶来应用吧！
代码：
//青蛙跳台阶递归法
public static void main(String[] args) {
System.out.println(jumpFloor(6));
}
public static int jumpFloor(int n){
int jumpNum=0;//方法总数
if(n==0){
return 0;
}
if (n==1){
return 1;
}
if (n==2){
return 2;
}else {
jumpNum=jumpFloor(n-1)+jumpFloor(n-2);
}
return jumpNum;
}
非递归法：
先看看图一中的方法数，是不是有种似曾相识的感觉，没错，类似于斐波那契数列(斐波那契数列为1、1、2、3、5、8、13、21、34……此数列从第3项开始，每一项都等于前两项之和，递推公式为F(n)=F(n-1)+F(n-2)，n≥3，F(1)=1，F(2)=1。)这里的方法数的分布为(1、 2 、3、 5、 8、 13…),从第三项开始，每一项都等于前两项的和。
分析过程：
代码：
//青蛙跳台阶非递归法
public static void main(String[] args) {
System.out.println(jump(5));
}
//一层台阶时有f1种方法
//两层台阶时有f2种方法
public static int jump(int n) {
int num = 0;
int f1 = 1;
int f2 = 2;
if(n==0){
return 0;
}
if(n==1){
return 1;
}if (n==2){
return 2;
}
for (int i = 3; i <= n; i++) {
num = f1 + f2;
f1 = f2;
f2 = num;
}
return num;
}
