面試題：Fibonacci數列

題目描述：大家都知道斐波那契數列，現在要求輸入一個整數n，請你輸出斐波那契數列的第n項（從0開始，第0項為0）。

方法1：遞歸

public class Solution {public int Fibonacci(int n) {if (n == 0){return 0;} else if(n == 1){return 1;} else{return Fibonacci(n - 1) + Fibonacci(n - 2);}}
}

方法2：循環

public class Solution {public int Fibonacci(int n) {if(n == 0){return 0;}else if(n == 1){return 1;}else{int a = 0;int b = 1;int f = 0;for(int i=1;i<n;i++){f = a + b;a = b;b = f;}return f;}}
}

遞歸是函數調用函數自身，循環是通過初始值和終止條件在一個范圍內重復計算

基于遞歸實現的函數代碼簡單，但性能不如基于循環的方法，如果沒有別的要求優先使用遞歸

遞歸的缺點是函數的調用有時間和空間的消耗，并且遞歸中有許多重復的計算

類似題目：一只青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法（先后次序不同算不同的結果）。

public class Solution {public int JumpFloor(int target) {if(target == 0){return 0;}else if(target == 1){return 1;}else if(target == 2){return 2;}else{//遞歸//return JumpFloor(target-1)+JumpFloor(target-2);//循環int a = 1;int b = 2;int J = 0;for(int i=2;i<target;i++){J = a + b;a = b;b = J;}return J;}}
}

類似題目：一只青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的臺階總共有多少種跳法（數學歸納法2的n-1次方）。

public class Solution {public int JumpFloorII(int target) {return (int)Math.pow(2,(target-1));}
}

?