定義：遞歸算法是一種直接或者間接調用自身函數或者方法的算法。
算法中使用遞歸可以很簡單地完成一些用循環實現的功能，比如二叉樹的左中右序遍歷。遞歸在算法中有非常廣泛的使用，包括現在日趨流行的函數式編程。
純粹的函數式編程中沒有循環，只有遞歸。
接下來我們來講解一下遞歸。通俗來說，遞歸算法的實質是把問題分解成規模縮小的同類問題的子問題，然後遞歸調用方法來表示問題的解
遞歸的三個要素一個問題的解可以分解為幾個子問題的解
子問題的求解思路除了規模之外，沒有任何區別
有遞歸終止條件
我這裡列舉了幾道算法題目，這幾道算法題目都可以用遞歸輕鬆寫出來：
動態規劃如果說遞歸是從問題的結果倒推，直到問題的規模縮小到尋常。那麼動態規劃就是從尋常入手， 逐步擴大規模到最優子結構。 這句話需要一定的時間來消化,如果不理解，可以過一段時間再來看。
遞歸的解決問題非常符合人的直覺，代碼寫起來比較簡單。但是我們通過分析（可以嘗試畫一個遞歸樹），可以看出遞歸在縮小問題規模的同時可能會重複計算。 中 我通過遞歸的方式來解決這個問題，同時內部維護了一個緩存來存儲計算過的運算，那麼我們可以減少很多運算。這其實和動態規劃有著異曲同工的地方。
我們結合求和問題來講解一下, 題目是給定一個數組，求出數組中所有項的和，要求使用遞歸實現。
代碼：
function sum(nums) {
if (nums.length === 0) return 0;
if (nums.length === 1) return nums[0];
return nums[0] + sum(nums.slice(1));
}
我們用遞歸樹來直觀地看一下。
這種做法本身沒有問題，但是每次執行一個函數都有一定的開銷，拿 JS 引擎執行 JS 來說，每次函數執行都會進行入棧操作，並進行預處理和執行過程，所以對於內存來說是一個挑戰。很容易造成爆棧。
瀏覽器中的 JS 引擎對於代碼執行棧的長度是有限制的，超過會爆棧，拋出異常。
我們再舉一個更加明顯的例子，問題描述：
一個人爬樓梯，每次只能爬 1 個或 2 個臺階，假設有 n 個臺階，那麼這個人有多少種不同的爬樓梯方法？
代碼：
function climbStairs(n) {
if (n === 1) return 1;
if (n === 2) return 2;
return climbStairs(n - 1) + climbStairs(n - 2);
}
這道題和 fibnacci 數列一模一樣，我們繼續用一個遞歸樹來直觀感受一下：
可以看出這裡面有很多重複計算，我們可以使用一個 hashtable 去緩存中間計算結果，從而省去不必要的計算。那麼動態規劃是怎麼解決這個問題呢？答案就是「查表」。
剛才我們說了遞歸是從問題的結果倒推，直到問題的規模縮小到尋常。動態規劃是從尋常入手， 逐步擴大規模到最優子結構。
從剛才的兩個例子，我想大家可能對前半句話有了一定的理解，我們接下來講解下後半句。
如果爬樓梯的問題，使用動態規劃，代碼是這樣的：
function climbStairs(n) {
if (n === 1) return 1;
if (n === 2) return 2;
let a = 1;
let b = 2;
let temp;
for (let i = 3; i <= n; i++) {
temp = a + b;
a = b;
b = temp;
}
return temp;
}
動態規劃的查表過程如果畫成圖，就是這樣的：
虛線代表的是查表過程
這道題目是動態規劃中最簡單的問題了，因為設計到單個因素的變化，如果涉及到多個因素，就比較複雜了，比如著名的背包問題，挖金礦問題等。
對於單個因素的，我們最多只需要一個一維數組即可，對於如背包問題我們需要二維數組等更高緯度。
爬樓梯我們並沒有使用一維數組，而是藉助兩個變量來實現的，空間複雜度是 O(1).之所以能這麼做，是因為爬樓梯問題的狀態轉移方程只和前兩個有關，因此只需要存儲這兩個即可。動態規劃問題有時候有很多這種討巧的方式，但並不是所有的
動態規劃的兩個要素狀態轉移方程
臨界條件
在上面講解的爬樓梯問題中
f(1) 與 f(2) 就是【邊界】
f(n) = f(n-1) + f(n-2) 就是【狀態轉移公式】
動態規劃問題要畫表格，但是有的人不知道為什麼要畫，就覺得這個是必然的，必要要畫表格才是動態規劃。
其實動態規劃本質上是將大問題轉化為小問題，然後大問題的解是和小問題有關聯的，換句話說大問題可以由小問題進行計算得到。
這一點是和遞歸一樣的， 但是動態規劃是一種類似查表的方法來縮短時間複雜度和空間複雜度。
畫表格的目的就是去不斷推導，完成狀態轉移， 表格中的每一個cell都是一個小問題， 我們填表的過程其實就是在解決問題的過程，我們先解決規模為尋常的情況，然後根據這個結果逐步推導，通常情況下，表格的右下角是問題的最大的規模，也就是我們想要求解的規模。
比如我們用動態規劃解決背包問題， 其實就是在不斷根據之前的小問題A[i - 1][j] A[i -1][w - wj]來詢問：
我是應該選擇它
還是不選擇它
至於判斷的標準很簡單，就是價值最大，因此我們要做的就是對於選擇和不選擇兩種情況分別求價值，然後取最大，最後更新cell即可。
相關問題太多了，沒有逐一列舉
總結本篇文章總結了算法中比較常用的兩個方法 - 遞歸和動態規劃。
如果你只能藉助一句話，那麼請記住：遞歸是從問題的結果倒推，直到問題的規模縮小到尋常。動態規劃是從尋常入手， 逐步擴大規模到最優子結構。