Recursion vs Iteration
對程序員來說渺鹦，遞歸應(yīng)該是一個與生俱來的思想（a built-in thought）沪曙，可以通過一個簡單的例子來說明鹊奖。
問題： 有n步臺階吠裆，一次只能上1步或2步渐逃，共有多少種走法扩所。
步驟1:找到走完前n步臺階和前n-1步臺階之間的關(guān)系。
為了走完n步臺階朴乖，只有兩種方法：從n-1步臺階爬1步走到或從n-2步臺階處爬2步走到。如果f(n)是爬到第n步臺階的方法數(shù)助赞，那么f(n) = f(n-1) + f(n-2)买羞。
步驟2: 確保開始條件是正確的。
f(0) = 0;
f(1) = 1;
public static int f(int n){
if(n <= 2) return n;
int x = f(n-1) + f(n-2);
return x;
}
遞歸方法的時間復(fù)雜度是n的指數(shù)級雹食，因為有很多冗余的計算畜普，如下：
f(5)
f(4) + f(3)
f(3) + f(2) + f(2) + f(1)
f(2) + f(1) + f(1) + f(0) + f(1) + f(0) + f(1)
f(1) + f(0) + f(1) + f(1) + f(0) + f(1) + f(0) + f(1)
來源? ? http://blog.csdn.net/lishk314/article/details/45739899
