遞歸的概述
摘取維基百科關于遞歸的描述：遞歸（英語：Recursion），又譯為遞回，在數(shù)學與計算機科學中，是指在函數(shù)的定義中使用函數(shù)自身的方法。遞歸一詞還較常用于描述以自相似方法重復事物的過程。例如，當兩面鏡子相互之間近似平行時，鏡中嵌套的圖像是以無限遞歸的形式出現(xiàn)的。也可以理解為自我復制的過程。
- 舉個語言例子：
大雄在房里，用時光電視看著從前的情況。電視畫面中的那個時候，他正在房里，用時光電視，看著從前的情況。電視畫面中的電視畫面的那個時候，他正在房里，用時光電視，看著從前的情況……
偽代碼：
func1() {
大雄在房里，用時光電視看著從前的情況。電視畫面中的那個時候，他正在房里，用時光電視，看著 從前的情況。電視畫面中的電視畫面的那個時候，他正在房里，用時光電視，看著從前的情況……
func1()
}
程序員眼中的遞歸
遞歸是指在函數(shù)的定義中使用函數(shù)自身的方法。
遞歸有兩層含義：
- 遞歸問題必須可以分解為若干個規(guī)模較小、與原問題形式相同的子問題。并且這些子問題可以用完全相同的解題思路來解決；
- 遞歸問題的演化過程是一個對原問題從大到小進行拆解的過程，并且會有一個明確的終點（臨界點）。一旦原問題到達了這個臨界點，就不用再往更小的問題上拆解了。最后，從這個臨界點開始，把小問題的答案按照原路返回，原問題便得以解決。
這里舉個用遞歸求n的階乘的例子：
上代碼：
func factorial(_ n: Int)->Int {
if 1 == n {
return n;
} else {
return factorial(n-1) * n
}
}
這里n傳入5，把式子展開如下：
factorial簡化為f
factorial(5)
=> 5 * f(4)
=> 5 * f(4 * f(3))
=> 5 * f(4 * f(3 * f(2)))
=> 5 * f(4 * f(3 * f(2 * f(1))))
=> 5 * f(4 * f(3 * f(2 * 1))
=> 5 * f(4 * f(3 * 2))
=> 5 * f(4 * 6)
=> 5 * 24
=> 120
圖形簡化如下：
看圖理解遞歸就是，先一步步往下遞，然后回歸，回歸的起點就是達到終止條件的時候。
遞歸的基本思想就是把規(guī)模大的問題轉(zhuǎn)化為規(guī)模小的相同的子問題來解決。 在函數(shù)實現(xiàn)時，因為大問題和小問題是一樣的問題，因此大問題的解決方法和小問題的解決方法也是同一個方法。這就產(chǎn)生了函數(shù)調(diào)用它自身的情況，這也正是遞歸的定義所在。
用遞歸解決問題的函數(shù)必須有明確的結束條件，否則就會導致無限遞歸的情況。總結起來，遞歸的實現(xiàn)包含了兩個部分，一個是遞歸主體，另一個是終止條件。
遞歸的算法思想
遞歸的數(shù)學模型其實就是數(shù)學歸納法，這個證明方法是我們高中時期解決數(shù)列問題最常用的方法。接下來，我們通過一道題目簡單回顧一下數(shù)學歸納法。
一個常見的題目是：證明當 n 等于任意一個自然數(shù)時某命題成立。
當采用數(shù)學歸納法時，證明分為以下 2 個步驟：
- 證明當 n = 1 時命題成立；
- 假設 n = m 時命題成立，那么嘗試推導出在 n = m + 1 時命題也成立。
與數(shù)學歸納法類似，當采用遞歸算法解決問題時，我們也需要圍繞這 2 個步驟去做文章：
- 當你面對一個大規(guī)模問題時，如何把它分解為幾個小規(guī)模的同樣的問題；
- 當你把問題通過多輪分解后，最終的結果，也就是終止條件如何定義。
所以當一個問題同時滿足以下 2 個條件時，就可以使用遞歸的方法求解：
- 可以拆解為除了數(shù)據(jù)規(guī)模以外，求解思路完全相同的子問題；
- 存在終止條件。
遞歸的案例
1，前序遍歷二叉樹，如下圖所示：
解題步驟:
- 對樹中的任意結點來說，先打印這個結點，然后前序遍歷它的左子樹，最后前序遍歷它的右子樹。
代碼如下：
func preOrderTraverse(_ root: TreeNode?) {
//終止條件
guard let rt = root else {
return
}
//遍歷步驟
print("node:(rt.val)")
preOrderTraverse(rt.left)
preOrderTraverse(rt.right)
}
2，漢諾塔問題是源于印度一個古老傳說的益智玩具。大梵天創(chuàng)造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著 64 片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上，并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。
解題步驟:
- 假設 n = 1,只有一個盤子，很簡單，直接把它從 A 中拿出來，移到 C 上；
- 如果 n = 2 呢？這時候我們就要借助 B 了，因為小盤子必須時刻都在大盤子上面，共需要 4 步。
如果 n > 2 呢？思路和上面是一樣的，我們把 n 個盤子也看成兩個部分，一部分有 1 個盤子，另一部分有 n - 1 個盤子。
那 n - 1 個盤子是怎么從 A 移到 C 的呢？
注意，當你在思考這個問題的時候，就將最初的 n 個盤子從 A 移到 C 的問題，轉(zhuǎn)化成了將 n - 1 個盤子從 A 移到 C 的問題， 依次類推，直至轉(zhuǎn)化成 1 個盤子的問題時，問題也就解決了。這就是分治的思想。
而實現(xiàn)分治思想的常用方法就是遞歸。不難發(fā)現(xiàn)，如果原問題可以分解成若干個與原問題結構相同但規(guī)模較小的子問題時，往往可以用遞歸的方法解決。具體解決辦法如下：
n = 1 時，直接把盤子從 A 移到 C；
-
n > 1 時，
- 先把上面 n - 1 個盤子從 A 移到 B（子問題，遞歸）；
- 再將最大的盤子從 A 移到 C；
- 再將 B 上 n - 1 個盤子從 B 移到 C（子問題，遞歸）。
代碼如下：
class Solution {
func hanota(_ A: inout [Int], _ B: inout [Int], _ C: inout [Int]) {
let n = A.count
move(n, &A, &B, &C)
}
func move(_ n:Int,_ A: inout [Int], _ B: inout [Int], _ C: inout [Int]) {
if n == 1{
C.append(A[A.count-1])
A.removeLast()
return
}
else{
move(n-1,&A, &C, &B)
C.append(A[A.count-1])
A.removeLast()
move(n-1,&B, &A, &C)
}
}
}
總結
遞歸的核心思想是把規(guī)模大的問題轉(zhuǎn)化為規(guī)模小的相似的子問題來解決。
在函數(shù)實現(xiàn)時，因為解決大問題的方法和解決小問題的方法往往是同一個方法，所以就產(chǎn)生了函數(shù)調(diào)用它自身的情況。另外這個解決問題的函數(shù)必須有明顯的結束條件，這樣就不會產(chǎn)生無限遞歸的情況了。遞歸的應用非常廣泛，很多數(shù)據(jù)結構和算法的編碼實現(xiàn)都要用到遞歸，例如分治策略、快速排序等等。
