淺出

為了描述問題的某一狀態(tài)，必須用到該狀態(tài)的上一狀態(tài)，而描述上一狀態(tài)，又必須用到上一狀態(tài)的上一狀態(tài)……這種用自已來定義自己的方法，稱為遞歸定義。形式如 f(n) = n * f(n - 1), if n = 0, f(n) = 1.

從問題的某一種可能出發(fā)，搜索從這種情況出發(fā)所能達(dá)到的所有可能，當(dāng)這一條路走到“盡頭”的時候，再倒回出發(fā)點(diǎn)，從另一個可能出發(fā)，繼續(xù)搜索。這種不斷“反悔”尋找解的方法，稱作“回溯法”。

深入

遞歸法好比是一個軍隊要通過一個迷宮，到了第一個分岔口，有 3 條路，將軍命令 3 個小隊分別去探哪條路能到出口，3 個小隊沿著 3 條路分別前進(jìn)，各自到達(dá)了路上的下一個分岔口，于是小隊長再分派人手各自去探路——只要人手足夠（對照而言，就是計算機(jī)的堆棧足夠），最后必將有人找到出口，從這人開始只要層層上報直屬領(lǐng)導(dǎo)，最后，將軍將得到一條通路。所不同的是，計算機(jī)的遞歸法是把這個并行過程串行化了。

而回溯法則是一個人走迷宮的思維模擬，其實是一種試探，走錯了倒回來，繼續(xù)走。該方法放棄關(guān)于問題規(guī)模大小的限制，并將問題的方案按某種順序逐一枚舉和試驗。發(fā)現(xiàn)當(dāng)前方案不可能有解時，就選擇下一個方案，倘若當(dāng)前方案不滿足問題的要求時，繼續(xù)擴(kuò)大當(dāng)前方案的規(guī)模，并繼續(xù)試探。如果當(dāng)前方案滿足所有要求時，該方案就是問題的一個解。放棄當(dāng)前方案，尋找下一方案的過程稱為回溯。

遞歸算法依賴與前一步的結(jié)果，它的結(jié)果來源于一條主線，是確定的，而不是試探的結(jié)果，這就是其與回溯的區(qū)別，而在很多情況下，回溯與遞歸算法是在一起使用的。

栗子

遞歸會出現(xiàn)在子程序中自己調(diào)用自己或間接地自己調(diào)用自己。最直接的遞歸應(yīng)用就是計算連續(xù)數(shù)的階乘，計算規(guī)律：n! = (n - 1)! * n。觀察階乘計算的規(guī)律，前一個數(shù)結(jié)成的結(jié)果可以直接被應(yīng)用到后一個數(shù)結(jié)成的計算中。

回溯是一種算法思想，可以用遞歸實現(xiàn)。通俗點(diǎn)講回溯就是一種試探，類似于窮舉，但回溯有“剪枝”功能，比如求和問題。給定 7 個數(shù)字，1 2 3 4 5 6 7 求和等于 7 的組合，從小到大搜索，選擇 1 + 2 + 3 + 4 = 10 > 7，已經(jīng)超過了 7，之后的 5 6 7 就沒必要在繼續(xù)了，這就是一種搜索過程的優(yōu)化。比如 8 皇后問題。