電腦科學之演算法——你不得不知的遞歸
- 2020 年 3 月 6 日
- 筆記
遞歸
本系列文章在Github:StevenEco以及WarrenRyan同步更新
簡介
程式調用自身的編程技巧稱為遞歸 (recursion) 。遞歸做為一種演算法在程式設計語言中廣泛應用。 一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法，它通常把一個大型複雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略只需少量的程式就可描述出解題過程所需要的多次重複計算，大大地減少了程式的程式碼量。遞歸的能力在於用有限的語句來定義對象的無限集合。一般來說，遞歸需要有邊界條件、遞歸前進段和遞歸返回段。當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回。
小例子
看著很抽象？那麼我們舉一個具體的例子：假設有一天，你正在學校上課，你坐在最後一排，突然你有一件重要的事情需要和第一排的同學進行溝通，你又不能隨意走動，那麼你應該怎麼解決呢？於是你寫了一個小紙條，給你前面的同學，並且告訴他轉交給第一排的同學，於是前排同學又將小紙條遞給了他的前排，循環往複，直到第一排的同學收到小紙條。第一排的同學看完小紙條，寫了他要對你說的話，於是他又將紙條遞給他的后座，一直遞到你為止。這個小例子就是遞歸的本質思想，你的小紙條就是參數，而傳遞的過程，事實上都是在執行傳遞函數的本身。
如果用程式語言來體現剛才的小例子，那麼程式碼就是
string Deliver(int row,string msg) { if(row == 1) { return "Read:" + msg; } return Deliver(--row,msg); }再舉一個例子，斐波那契數列是一個很常見的數列，它的通項公式是 (f(n+2) = f(n) + f(n+1)),我們可以發現，它並沒有提及斐波那契數列的表達式，而是給了一個抽象的函數遞推式，那麼這個時候我們就可以使用遞歸，將問題簡化成一個遞推的內容而不是具體的實現。用程式碼則是
int fib(int n) { if(n == 1 || n == 2) { return 1 } return fib(n-1) + fib(n-2); }通常，遞歸必須擁有遞推式和跳出條件，因為這可以保證函數不會爆棧，我們要從三個角度去做一個遞歸：
- 遞歸的定義：接受什麼參數，返回什麼值，代表什麼意思 。當函數直接或者間接調⽤⾃⼰時，則發⽣了遞歸
- 遞歸的拆解：每次遞歸都是為了讓問題規模變⼩
- 遞歸的出⼝：必須有⼀個明確的結束條件。因為遞歸就是有「遞」有「歸」，所以必須又有一個明確的點，到了這個點，就不用「遞下去」，而是開始「歸來」。
總而言之，遞歸就是儘可能忽略函數內部的實現，主要關注函數整體需要做的事情。
遞歸的本質
通過上述的小例子，你可能已經理解了遞歸的含義，但是為什麼通過函數調用函數這種「詭異」的操作可以實現我們的內容呢？如果你在閱讀本篇文章之前已經有了一些基礎的數據結構和程式語言知識，那麼你會知道函數的調用是在棧中實現的，當函數嵌套調用時，系統會將這些函數壓入棧中，而棧是先進後出的性質，那麼當遞歸調用時，會一次性將函數壓棧到可以return的那個子函數，然後子函數執行完畢返回後，再將返回值帶給父函數，再執行父函數。也就是說，遞歸其實就是一個隱式的棧。
通過這個進棧出棧的過程，一個大的抽象問題就被分解成了若干個嵌套的子問題，子問題一層一層被解決，直到最後一個起始層。
簡單的解釋就是，遞歸事實上也是兩個問題
遞：將問題不斷細化直到最小，例如斐波那契數列的問題，fib(5)在程式中的遞大致是
fib(5) = fib(4) + fib(3); fib(5) = (fib(3) + fib(2)) + (fib(2) + fib(1)) fib(5) = ((fib(2) + fib(1)) + fib(2)) + (fib(2) + fib(1));歸過程就是將上述遞過程的子問題逐步返回到頂層。
整個過程和我們往第一排傳紙條再傳回來是完全一致的。
遞歸的用途
我們會發現遞歸非常的節省程式碼，而且看起來似乎也沒有空間損耗。但真的是這樣的嗎？答案肯定是否的。誠然，遞歸會讓程式碼的簡潔程度和可讀性大幅上漲（可讀性上升，但是並不容易被理解和Debug），但是遞歸也並不是什麼時候都是好的。
首先遞歸最常用的地方就是鏈表、樹、圖等含指針的數據結構的操作和計算，因為在這種地方，使用隊列、棧等輔助的數據結構會使得程式碼非常長，並且對於許多演算法羸弱的碼農並不容易寫出來。例如樹的中序遍歷，對於非遞歸的方法，你需要藉助棧，並且嚴格的需要保證入棧順序。而對於後序遍歷，你可能還需要藉助哈希表來保證左右節點已經被訪問，這顯然不好。對於遞歸，只有短短的幾行
void InOrder(Tree tree) { if (tree == null) return; InOrder(tree.Left); Console.WriteLine(tree.Value); InOrder(tree.Right); } void PostOrder(Tree tree) { if (tree == null) return; PostOrder(tree.Left); PostOrder(tree.Right); Console.WriteLine(tree.Value); }相比於普通的程式碼顯得更加簡潔明了。
自頂向下與自底向上
但是有時候遞歸會造成嚴重的性能問題，尤其會導致棧溢出的問題，事實上函數本身壓棧是並不消耗什麼空間的，因為本身只是一個指針，並不需要存儲任何內容。但是存在返回值的時候，函數需要將返回值保存，因此一同申請空間。當函數棧過深的時候，存儲的子函數的返回值也會越來越多，你可以試試將上述斐波那契數列的程式碼參數設置為一個很大的數字，你會發現程式非常慢，並且有可能會導致棧溢出從而強制退出。因為你從上述分析的遞歸過程你會發現，有些函數被重複運算了，例如fib(2)就被計算了多次，而這是不需要的。因此浪費了時間和空間。
自頂向下
啥是自頂向下的方法？頂就是頂層任務，也就是我們的預期結果，向下就是指分解成小任務。自頂向下就是講大任務拆解成若干小任務，隨後將小任務組合起來的過程。
通常來說自頂向下有時會造成嚴重的性能問題，例如我們舉的例字，假設你只是想讓第一排的同學把橡皮給你，資訊卻傳遞了整整一個來回。假設第一排的同學一開始就知道要把橡皮給你，那麼就能節省不少時間。
事實上對於斐波那契數列而言，我們並不關心他的前面項的結果，並且在前文的敘述中你也發現了有重複計算的問題。例如fib(10)的值，你完全沒有必要關心fib(5)之類的是多少，你只需要關心fib(8)+fib(9)而已，因此對於fib(5)的值你也是完全沒有必要壓棧的。遞歸的斐波那契數列時間複雜度達到了驚人的(O(2^n)),空間也用了(S(n))。
假設一個任務可以拆分成互相不干擾，沒有直接聯繫的多個子任務，那麼自頂向下的方法則是最優的方法，例如樹的遍歷，對於一個節點而言，它的兄弟節點必然不會是他的子節點（子函數的結果），那麼你就可以大膽的用自頂向下的遞歸。而對於斐波那契數列，你會發現他的子任務顯然會建立聯繫，那麼自頂向下的方法必然會導致重複的運算，甚至爆棧。
自底向上
為了解決子任務相關聯導致的自頂向下的性能問題，我們引出自底向上的方法。自底向上則是將最小的子任務往大任務組合，這樣就不會有重複計算的過程，因為子任務組合過程是單向的。
對於下面這個改良版的斐波那契數列，儘管程式碼顯得並不是那麼可讀和方便，但是時間複雜度卻降到了(O(n)),並且只使用了常數個的空間。顯然我們的複雜度下降了。
int fib(int n) { int rs = 0; int[] temp = new int []{ 1, 1 }; for (int i = 2; i < n; i++) { rs = temp[0] + temp[1]; temp[0] = temp[1]; temp[1] = rs; } return rs; }並且對於斐波那契數列這種存在通項公式的遞歸,使用通項公式會使得你的時間複雜度進一步下降至(O(logn))以下。因此可見遞歸雖好，但可不要濫用。
但是自底向上並不是任何時候都是有效的，例如最小子任務不可知的情況下，樹還是一個很好的例子，對於樹的葉子結點，在父節點未知的情況下必然無法確定，因此自底向上失效。
小題目
為了加深各位對遞歸的理解，這裡選取了幾個使用遞歸解決的小題目，希望你能獨立解決難題，答案將會在文末解析。請使用遞歸解決嗷！你可以將程式碼在評論中留下，我會仔細審閱，輸入特殊用例來判斷你的正確性。
- Code1 – 反轉字元串:
//給你一個字元串，請將其反轉。 //輸入 Hello //輸出 olleH public static string Reverse(string str) { }- Code2 – 三個一組交換單鏈表
//給你一個單鏈表，請返回三個一組反轉後單鏈表的表頭 //輸入：1->2->3->4->5 //返回：3->2->1->4->5 class LinkNode { public int Value { get; set;} public LinkNode Next { get; set;} } public LinkNode Reverse(LinkNode head) { }- Code3 – 斐波那契數列
//使用遞歸計算斐波那契數列 //要求時間複雜度降為O(n) //Tip:驗證時間複雜度可以輸入一個50000去跑 public int Fib(int n) { }如果我的文章幫助了你，請幫我點個贊，給個star，關注三連走一波。
