一文學會遞歸解題
遞歸的實戰演練（入門級）
熱身賽
輸入一個正整數n，輸出n!的值。其中n!=123…n,即求階乘
套用上一節我們說的遞歸四步解題套路來看看怎麼解：
1.定義這個函數，明确這個函數的功能，我們知道這個函數的功能是求 n 的階乘, 之後求 n-1, n-2 的階乘就可以調用此函數了
/**
* 求 n 的階乘
*/
public int factorial(int n) {
} 2.尋找問題與子問題的關系 階乘的關系比較簡單， 我們以 f(n) 來表示 n 的階乘， 顯然 f(n) = n * f(n - 1), 同時臨界條件是 f(1) = 1,即
3. 将第二步的遞推公式用代碼表示出來補充到步驟 1 定義的函數中
/**
* 求 n 的階乘
*/
public int factorial(int n) {
// 第二步的臨界條件
if (n < =1) {
return1;
}
// 第二步的遞推公式
return n * factorial(n-1)
} 4.求時間複雜度 由于 f(n) = n f(n-1) = n (n-1) .... f(1),總共作了 n 次乘法，是以時間複雜度為 n。
看起來是不是有這麼點眉目， 當然這道題确實太過簡單,很容易套路，那我們再來看進階一點的題。
入門題
一隻青蛙可以一次跳 1 級台階或一次跳 2 級台階,例如:
跳上第 1 級台階隻有一種跳法：直接跳 1 級即可。跳上第 2 級台階
有兩種跳法：每次跳 1 級，跳兩次；或者一次跳 2 級。
問要跳上第 n 級台階有多少種跳法？
我們繼續來按四步曲來看怎麼套路。
1.定義一個函數，這個函數代表了跳上 n 級台階的跳法
/**
* 跳 n 極台階的跳法
*/
public int f(int n) {
} 2.尋找問題與子問題之前的關系 這兩者之前的關系初看确實看不出什麼頭緒，但仔細看題目，一隻青蛙隻能跳一步或兩步台階，自上而下地思考，也就是說如果要跳到 n 級台階隻能從 從 n-1 或 n-2 級跳， 是以問題就轉化為跳上 n-1 和 n-2 級台階的跳法了，如果 f(n) 代表跳到 n 級台階的跳法，那麼從以上分析可得 f(n) = f(n-1) + f(n-2),顯然這就是我們要找的問題與子問題的關系,而顯然當 n = 1, n = 2， 即跳一二級台階是問題的最終解，于是遞推公式系為
3.将第二步的遞推公式用代碼表示出來補充到步驟 1 定義的函數中 補充後的函數如下
/**
* 跳 n 極台階的跳法
*/
public int f(int n) {
if (n == 1) return1;
if (n == 2) return2;
return f(n-1) + f(n-2)
} 4.計算時間複雜度 由以上的分析可知 f(n) 滿足以下公式
斐波那契的時間複雜度計算涉及到高等代數的知識， 這裡不做詳細推導，有興趣的同學可以點選
這裡檢視,我們直接結出結論。
由些可知時間複雜度是指數級别，顯然不可接受，那回過頭來看為啥時間複雜度這麼高呢,假設我們要計算 f(6),根據以上推導的遞歸公式，展示如下
可以看到有大量的重複計算, f(3) 計算了 3 次， 随着 n 的增大，f(n) 的時間複雜度自然呈指數上升了
5.優化
既然有這麼多的重複計算，我們可以想到把這些中間計算過的結果儲存起來，如果之後的計算中碰到同樣需要計算的中間态，直接在這個儲存的結果裡查詢即可，這就是典型的 以空間換時間,改造後的代碼如下
public int f(int n) {
if (n == 1) return1;
if (n == 2) return2;
// map 即儲存中間态的鍵值對， key 為 n，value 即 f(n)
if (map.get(n)) {
return map.get(n)
}
return f(n-1) + f(n-2)
} 那麼改造後的時間複雜度是多少呢，由于對每一個計算過的 f(n) 我們都儲存了中間态 ，不存在重複計算的問題，是以時間複雜度是 O(n), 但由于我們用了一個鍵值對來儲存中間的計算結果，是以空間複雜度是 O(n)。問題到這裡其實已經算解決了，但身為有追求的程式員，我們還是要問一句,空間複雜度能否繼續優化?
6.使用循環疊代來改造算法 我們在分析問題與子問題關系（f(n) = f(n-1) + f(n-2)）的時候用的是自頂向下的分析方式,但其實我們在解 f(n) 的時候可以用自下而上的方式來解決，通過觀察我們可以發現以下規律
f(1) = 1
f(2) = 2
f(3) = f(1) + f(2) = 3
f(4) = f(3) + f(2) = 5
....
f(n) = f(n-1) + f(n-2) 最底層 f(1), f(2) 的值是确定的，之後的 f(3), f(4) ,...等問題都可以根據前兩項求解出來，一直到 f(n)。是以我們的代碼可以改造成以下方式
public int f(int n) {
if (n == 1) return1;
if (n == 2) return2;
int result = 0;
int pre = 1;
int next = 2;
for (int i = 3; i < n + 1; i ++) {
result = pre + next;
pre = next;
next = result;
}
return result;
} 改造後的時間複雜度是 O(n), 而由于我們在計算過程中隻定義了兩個變量（pre，next），是以空間複雜度是O(1)
簡單總結一下：分析問題我們需要采用自上而下的思維，而解決問題有時候采用自下而上的方式能讓算法性能得到極大提升,思路比結論重要。
遞歸的實戰演練(進階級)
來源 | 五分鐘學算法
作者 | 碼海