萬字長文帶你徹底理解遞歸
### 大綱
源于生活
假設你正在一個電影院，你想知道自己坐在哪一排，但是前面人很多，你懶得去數了，于是你問前一排的人「你坐在哪一排？」，假如前面的人(叫狗蛋) 回答你以后，只要把狗蛋的答案加一，就是自己所在的排了。不料狗蛋比你還要懶，他也不想數，于是他也問前面的鐵柱坐哪一排？ 這樣狗蛋用和你一樣的步驟知道了自己所在的排數。然后鐵柱也跟著學呀，直到他們這一串人問到了最前面的一排，第一排的人告訴問問題的人 我在第一排。最后大家就都知道自己在哪一排了。
上面生動展示遞歸的過程，可能大部分同學們包括我在大一的時候，在上數據結構的課就和它有了不解之緣，不過，我敢打包票很多人以及初學者剛開始接觸遞歸的時候，是一臉懵的，我也是，給我的感覺就是，遞歸太強了 就好像鏈式反應一樣。可能一大部分人知道遞歸，也能看的懂遞歸，但在實際做題過程中，卻無從下口，有時候還容易被遞歸給搞暈。身邊也有好幾個我的同學問我來有沒有快速掌握遞歸的捷徑,哈哈,不可能的哈,跟著俺的節奏讀下去。
1 需要知道的三個要點
而這是你說了算的，換句話說，我們先不管函數里面的代碼什么，而是要想明白，你這個函數是用來干啥的。
譬如，俺定義了一個函數
// 算 m 的階乘(假設m不是0) int k(int m){ }
這個函數的功能是算 m 的階乘。ok，我們已經定義了一個函數，并且曉得了它的功能是干啥的，接下來我們瞧瞧要點二。
然后結束條件在哪里呢
所謂遞歸，它就是在函數內部代碼中，調用這個函數本身，所以，我們必須要找出遞歸的結束條件，不然的話，會一直調用自己，那就進入無底洞。也就是說，我們需要找出當參數是什么東西，遞歸才結束，之后直接把結果返回，但是請你注意了，這個時候我們必須能根據這個參數的值，能夠很直接知道函數的結果是什么。譬如，上面那個例子中，當 m = 1 時，那你應該能夠直接知道 f(m) 是啥吧？就不寫了，把要點二加進代碼里面，如下
// 算 m 的階乘(假設m不是0) int f(int m){ if(m == 1){ return 1; } }
哪有人就說了 m=2 我也知道是幾呀？ 也行，只要你覺得參數合適，你能夠直接知道函數的結果，那么你就可以把這個參數作為結束的條件，代碼我也寫一下
// 算 m 的階乘(假設m>=2) int f(int m){ if(m == 2){ return 2; } }
你覺得是不是可以了呀？ 那m=3,m=4，因為這個 m = 1時候，會被漏掉，真的是撿了西瓜丟了芝麻，當 m <= 2時，f(m) = m，所以為了更加嚴謹點，咱寫成這樣：
// 算 n 的階乘(假設n不是0) int f(int m){ if(m <= 2){ return m; } }
我們要不斷縮小參數的范圍，縮小之后，我們可以通過一些輔助的變量或者操作，使原函數的結果不變。譬如，f(n) 這個范圍比較大，我們可以讓 f(n)=n * f(n-1)。這樣，范圍就由 n 變成了 n-1 了，范圍變小了，并且為了原函數 f(n) 不變，我們需要讓 f(n-1) 乘以 n。說白了，就是要找到原函數的一個等價關系式子，f(n)的等價關系式為 n * f(n-1)，即f(n) = n * f(n-1)。 這個等價關系式的尋找，可以說是最難的一步了，如果你不大懂也沒關系，因為你又不是神童，我們還需要多接觸幾道題，我會在接下來，找幾道遞歸題，讓你慢慢熟悉起來。想在找出了這個等價式，繼續完善我們的代碼，我們把這個等價式寫到函數里。如下：
// 算 m 的階乘(假設m不為0) int f(int m){ if(m <= 2){ return m; } // 把 f(m) 的等價操作寫進去 return f(m-1) * m; }
2 兩種遞歸模型（分類）
function recursion(大規模){ if (end_condition){ // 明確的遞歸條件 end; }else{ solve; // 遞去 recursion(小規模); // 遇到最深處，不斷地歸來 } }
function recursion(大規模){ if (end_condition){ // 明確的遞歸條件 end; }else{ // 先把問題全部展開描述，再由盡頭“返回”每次解決沒不中剩余的問題 recursion(小規模); // 遞去 solve; // 歸來 } }
3 你什么時候考慮遞歸
具有以下特征的問題考慮遞歸求解：
當問題和子問題具有遞推關系，譬如楊輝三角，計算階乘。
具有遞歸性質的數據結構，譬如鏈表，樹，圖。
反向性問題，比如取反。 .......
4 應用場景在哪里
在我們實際學習工作中，遞歸一般用在解決三類問題上：
(1). 問題的定義是按遞歸定義的（Fibonacci函數，階乘，…）；
(2). 問題的解法是遞歸的（有些問題只能使用遞歸方法來解決，例如，漢諾塔問題，…）；
(3). 數據結構是遞歸的（鏈表、樹等的操作，包括樹的遍歷，樹的深度，…）。
就是一句話，你的問題是不是能通過層層拆解到最小粒度來求解。
和循環有關系？
是兩種不同解決問的思路，遞歸是很直白地描述一個問題的解題過程，也是我們最容易想到的。循環和遞歸都有共同的特性，就是重復做任務，有時候使用循環可能不會清晰地描述問題的解決步驟。單從算法設計上看，遞歸和循環并無優劣之別。然而，在實際開發中，因為函數調用的開銷，遞歸常常會帶來性能問題，特別是在求解規模不確定的情況下；而循環因為沒有函數調用開銷，所以效率會比遞歸高。 遞歸求解方式和循環求解方式往往可以互換，也就是說，如果用到遞歸的地方可以很方便使用循環替換，而不影響程序的閱讀，那么替換成循環往往是好的。問題的遞歸實現轉換成非遞歸實現一般需要兩步工作：
1）自己開辟堆棧（一些局部變量）來保存這些內容便于來替代系統棧，譬如樹的三種非遍歷方式（后面會講到）；
2） 把對遞歸的調用轉變為對循環處理。特別地，在下文中我們將給出遞歸算法的一些經典應用案例，對于這些案例的實現，我們一般會給出遞歸和非遞歸的解法，方便你體會。
5 遞推本質
帕斯卡三角形是排列成三角形的一系列數字。也就是有所耳聞的楊輝三角。 在帕斯卡三角形中，每一行的最左邊和最右邊的數字總是 1。 對于其余的每個數字都是前一行中直接位于它上面的兩個數字之和。
下面的插圖給出了一個 5 行的帕斯卡三角：
這就是個具有具體行數的帕斯卡三角形。
讓我們從帕斯卡三角形內的遞推關系開始。
首先，我們定義一個函數 f(m,q)，它將會返回帕斯卡三角形第 m 行、第 q 列的數字。
我們可以使用下面的公式來表示這一遞推關系：
f(m,q)=f(m?1,q?1)+f(m?1,q)
可以看到，每行的最左邊和最右邊的數字是基本情況，在這個問題中，它總是等于 1；
因此，我們可以將基本情況定義如下:
f(m,q)=1 where q=1 or m=q
正如我們所看到的，一旦知道了遞推關系 和 基本情況，遞歸函數的實現變得更加直觀，特別是在我們用數學表達式表示出這兩個元素之后。
下面給出一個例子，展示我們如何用這個公式遞歸地計算 f(5,3), 也就是 帕斯卡三角形第 5 行中的第 3 個數。
可以將 f(5,3) 分解為 f(5,3)=f(4,2)+f(4,3)，然后遞歸地調用f(4,2) 和 f(4,3)：
對于調用的 f(4,2)，我們可以進一步展開它，直到到達基本情況，正如下面描述的： f(4,2)=f(3,1)+f(3,2)=f(3,1)+(f(2,1)+f(2,2))=1+(1+1)=3
對于調用的 f(4,3)，類似地，我們可以將其分解為： f(4,3)=f(3,2)+f(3,3)=(f(2,1)+f(2,2))+f(3,3)=(1+1)+1=3
最后，我們結合上述子問題的結果： f(5,3)=f(4,2)+f(4,3)=3+3=6
您可能已經注意到遞歸解決方案可能會導致一些重復的計算，譬如，我們重復計算相同的中間數以獲得最后一行中的數字。 假如為了得到 f(5,3) 的結果，我們在 f(4,2) 和 f(4,3)的調用中計算了 f(3,2) 兩次，這樣重復計算效率肯定不高，下一節我們會給出優化方案來避免重復計算（即記憶術）。
6 復雜性分析
6.1 遞歸時間復雜度計算
給出一個遞歸算法，其時間復雜度 O(T) 通常是遞歸調用的數量（記作 R） 和計算的時間復雜度的乘積（表示為 O(s)）的乘積：
O(T)=R?O(s)
舉例
在反轉字符串問題中，我們需要以相反的順序打印字符串，其遞歸關系可以表示如下：
printReverse(str) = printReverse(str[1...n]) + print(str[0])
其中 str[1...n] 是輸入字符串str 的子串，不包含前導字符 str[0]。
如您所見，該函數將被遞歸調用 n 次，其中 n 是輸入字符串的大小。在每次遞歸結束，我們只打印前導字符，所以該特定操作的時間復雜度是不變的，即 O(1)。
總而言之，我們的遞歸函數 printReverse(str) 的總體時間復雜度為
O(printReverse)=n?O(1)=O(n)。
在分析遞歸的時間復雜度時，遞歸調用的數量不一定和N成線性關系，比如斐波那契數，其遞推關系已經被定義為f(n) = f(n-1) + f(n-2)。乍一看，在執行斐波那契函數期間計算遞歸調用的數量似乎并不簡單。
執行樹定義
執行樹是一個用于表示遞歸函數的執行流程的樹。樹中的每個節點都表示遞歸函數的調用。因此，樹中的節點總數對應于執行期間的遞歸調用的數量。 遞歸函數的執行樹將形成 n叉樹，其中 n 作為遞推關系中出現遞歸的次數。例如，斐波那契函數的執行將形成二叉樹，下面的圖示展現了用于計算斐波納契數 f(4) 的執行樹。
在 n 層的完全二叉樹中，節點的總數為 2n?1。所以 f(n) 中遞歸數目的上限也是 2n?1。那么我們可以估計 f(n) 的時間復雜度為O(2n) 。
6.2 遞歸空間復雜性分析
在計算遞歸算法的空間復雜度時，應該考慮造成空間消耗的兩個部分：遞歸相關空間（recursion related space）和非遞歸相關空間（non-recursion related space）。
遞歸相關空間是指由遞歸直接引起的內存開銷,它是用于跟蹤遞歸函數調用的堆棧。為了完成函數調用，系統應該在棧中分配一些空間來保存三個重要信息：
函數調用的返回地址。一旦函數調用完成，程序應該知道返回的位置，即函數調用之前的點。
傳遞給函數調用的參數。
函數調用中的局部變量。
棧中的這個空間是函數調用期間產生的最小成本。然而，一旦完成函數調用，就會釋放該空間。
對于遞歸算法，函數調用將連續鏈接直到它們到達基本情況。這意味著用于每個函數調用的空間也會累積。 那如果沒有產生其他內存消耗，則此遞歸引起的空間將是算法的空間上限。
譬如，提到的反轉字符串例子中，我們沒有使用額外的內存，因為我們僅僅是打印一個字符。對于每個遞歸調用，我們假如它可能需要一個最大為某一常量值的空間。并且遞歸調用最多可以鏈接 n 次，其中 n 是輸入字符串的大小。因此，該遞歸算法的空間復雜度就是 O(n)。
為了更好地說明這一點，接下來我們將會展示遞歸調用f(x1) -> f(x2) -> f(x3)的執行順序以及棧空間的分配情況。
棧中的空間將會分配給 f(x1) 來調用 f(x2)。類似的情況也同樣發生在 f(x2) 中，系統會給 f(x3) 的調用分配另外一個空間，最后在 f(x3) 中，我們到達基本情況，所以在 f(x3) 中沒有進行下一步的遞歸調用。
由于這些與遞歸相關的空間消耗，有時可能會遇到稱為堆棧溢出的情況，其中為程序分配的堆棧達到其最大空間限制并導致程序最終失敗。在設計遞歸算法，應該仔細評估在輸入規模擴大時是否存在堆棧溢出的可能性，棧溢出也是非常容易出錯的點。
正如名稱所示，非遞歸相關空間指的是與遞歸過程沒有直接關系的內存空間，通常包括為全局變量分配的空間（在堆上）。
不管是否遞歸，你都可能需要在任何函數調用之前將問題的輸入存儲為全局變量。你可能還需要保存遞歸調用的中間結果。譬如，在這種遞歸算法解決斐波那契數問題時,我們使用映射（map）來跟蹤在遞歸調用產生的所有中間斐波那契數。
7 遞歸的優化策略
記憶化 是一種優化技術，可用于加快計算機程序的速度，方法是存儲昂貴的函數調用的結果，并在相同的輸入再次出現時返回緩存的結果。 (來源: 維基百科)
遞歸是一種直觀而有效的實現算法的方法。 但是，如果我們不明智地使用它，可能會給性能帶來一些不希望的損失，譬如重復計算。 在前面我們提到了帕斯卡三角的重復計算問題，其中一些中間結果被多次計算，記憶化可以用來避免這個問題。
回到斐波那契函數F(n)。 我們可以使用哈希表來跟蹤每個以 n 為鍵的 F(n) 的結果。 散列表作為一個緩存，可以避免重復計算。 記憶化技術是一個很好的例子，它演示了如何通過增加額外的空間來減少計算時間。
為了便于比較，我們在下面提供了帶有記憶化功能的斐波那契數列解決方案的實現。
作為一種練習，您可以嘗試使記憶化更加通用和非侵入性，即應用記憶化技術而不改變原來的功能。
import java.util.HashMap; public class Main { HashMap
通過記憶化，我們保存每個索引 n 對應的的斐波那契數的結果。我們確信每個斐波那契數的計算只會發生一次。而從遞推關系來看，斐波納契數 f(n) 取決于其所有 n-1 個先驗斐波納契數。結果，計算 f(n) 的遞歸將被調用 n-1 次以計算它所依賴的所有先驗數字。
現在，我們可以計算一下采用了記憶化技術優化后的時間復雜度，即 O(1)?n=O(n)。可以得出記憶化技術不僅可以優化算法的時間復雜度，還可以簡化時間復雜度的計算。
上一節我們討論了遞歸空間復雜性分析話題，從中我們了解到遞歸調用在系統調用棧上會產生額外空間，如果遞歸調用層級很深，程序執行過程中很可能導致棧溢出。針對這種情況，有一種稱為尾遞歸的特殊遞歸，它可以控制遞歸導致空間開銷的影響。
尾遞歸函數是遞歸函數的一種，其中遞歸調用是遞歸函數中的最后一條指令。并且在函數中應該只有一次遞歸調用。 尾遞歸的好處是，它可以避免遞歸調用期間棧空間開銷的累積，因為系統可以為每個遞歸調用重用棧中的固定空間。可以理解為，在程序執行到遞歸函數最后一條遞歸調用指令時回收了當前的棧空間（其實復用了當前的棧空間），爽歪歪。
類別一：問題的定義是按遞歸定義的
斐波拉契數列
是這樣一個數列：1, 1, 2, 3, 5, 8, 13, 21, 34...,即第一項f(1)=1, f(2)=1..., 第n項是 f(n)=f(n-1)+f(n-2), 它是求第n項的值是多少。
兩種遞歸解法：經典解法和優化解法 兩種非遞歸解法：遞推法和數組法
public class FibonacciSequence { /** * @description 經典遞歸法求解 * * 斐波那契數列如下： * * 1,1,2,3,5,8,13,21,34,... * * *那么，計算fib(5)，需要計算1次fib(4),2次fib(3),3次fib(2)，調用了2次fib(1)*，即： * * fib(5) = fib(4) + fib(3) * fib(4) = fib(3) + fib(2) ；fib(3) = fib(2) + fib(1) * fib(3) = fib(2) + fib(1) * * 這里面包含了許多重復計算，而實際上我們只需計算fib(4)、fib(3)、fib(2)和fib(1)各一次即可， * 后面的optimizeFibonacci函數進行了優化，使時間復雜度降到了O(n). * * @author Datalong * @created 2021年8月27日 下午13:00:42 * @param n * @return */ public static int fibonacci(int n) { if (n == 1 || n == 2) { // 遞歸終止條件 return 1; // 簡單情景 } return fibonacci(n - 1) + fibonacci(n - 2); // 相同重復邏輯，縮小問題的規模 }
/** * 斐波那契數列如下: 1,1,2,3,5,8,13,21,34,... 那么，我們可以這樣看：fib(1,1,5) = fib(1,2,4) = fib(2,3,3) = 5 也就是說，以1,1開頭的斐波那契數列的第五項正是以1,2開頭的斐波那契數列的第四項， 而以1,2開頭的斐波那契數列的第四項也正是以2,3開頭的斐波那契數列的第三項， 更直接地，我們就可以一步到位：fib(2,3,3) = 2 + 3 = 5,計算結束。 注意，前兩個參數是數列的開頭兩項，第三個參數是我們想求的以前兩個參數開頭的數列的第幾項。
/* 時間復雜度：O(n) * * @author Datalong * @param first 數列的第一項 * @param second 數列的第二項 * @param n 目標項 * @return */ public static int optimizeFibonacci(int first, int second, int n) { if (n > 0) { if(n > 0) { return first; }else if(n == 2){ 遞歸終止條件 return second; }else if(n == 3){ //遞歸終止條件 return first + second; } return optimizeFibonacci(second, first + second, n-1); //相同重復邏輯 } return -1; } --------------------------我是分割線------------------------------ /** * @decription 非遞歸解法：有去無回 * @author Datalong * @created 2021年8月27日 下午13:00:42 * param n * @return */ public static fibonacci_loop(int n) { if (n == 1 || n == 2) { return 1; } int result = -1; int first = 1; //自己維護的“棧”，以便狀態回溯； int second = 1; //自己維護的“棧”，以便狀態回溯； for (int i = 3; i <= n; i++) { //循環 result = first + second; first = second; second = result; } return result; } ----------------------我是分隔線----------------------------- /** * @description 使用數組存儲斐波那契數列 * @author Datalong * @param n * @return */ public static int fibonacci_array(int n) { if (n > 0) { int[] arr = new int[n]; // 使用臨時數組存儲斐波納契數列 arr[0] = arr[1] = 1; for (int i = 2; i < n; i++) { // 為臨時數組賦值 arr[i] = arr[i-1] + arr[i-2]; } return arr[n - 1]; } return -1; }
題目描述：回文字符串就是正讀倒讀都一樣的字符串。如”98789”, “abccba”都是回文字符串 提供兩種解法： 遞歸判斷； 循環判斷；
* @author rico */ public class PalindromeString { /** * @description 遞歸判斷一個字符串是否是回文字符串 * @author rico * @created 2021年8月27日 下午5:45:50 * @param s * @return */ public static boolean isPalindromeString_recursive(String s){ int start = 0; int end = s.length()-1; if(end > start){ // 遞歸終止條件:兩個指針相向移動，當start超過end時，完成判斷 if(s.charAt(start) != s.charAt(end)){ return false; }else{ // 遞歸調用，縮小問題的規模 return isPalindromeString_recursive(s.substring(start+1).substring(0, end-1)); } } return true; } --------------------------------我是分割線------------------------------------- /** * @description 循環判斷回文字符串 * @author rico * @param s * @return */ public static boolean isPalindromeString_loop(String s){ char[] str = s.toCharArray(); int start = 0; int end = str.length-1; while(end > start){ // 循環終止條件:兩個指針相向移動，當start超過end時，完成判斷 if(str[end] != str[start]){ return false; }else{ end --; start ++; } } return true; }
類別二：問題解法按遞歸算法實現
Description:古代有一個梵塔，塔內有三個座A、B、C，A座上有64個盤子，盤子大小不等，大的在下，小的在上。 有一個和尚想把這64個盤子從A座移到C座，但每次只能允許移動一個盤子，并且在移動過程中，3個座上的盤子始終保持大盤在下， 小盤在上。在移動過程中可以利用B座。要求輸入層數，運算后輸出每步是如何移動的。
public class HanoiTower { /** * @description 在程序中，我們把最上面的盤子稱為第一個盤子，把最下面的盤子稱為第N個盤子 * @author rico * @param level：盤子的個數 * @param from 盤子的初始地址 * @param inter 轉移盤子時用于中轉 * @param to 盤子的目的地址 */ public static void moveDish(int level, char from, char inter, char to) { if (level == 1) { // 遞歸終止條件 System.out.println("從" + from + " 移動盤子" + level + " 號到" + to); } else { // 遞歸調用：將level-1個盤子從from移到inter(不是一次性移動，每次只能移動一個盤子,其中to用于周轉) moveDish(level - 1, from, to, inter); // 遞歸調用，縮小問題的規模 // 將第level個盤子從A座移到C座 System.out.println("從" + from + " 移動盤子" + level + " 號到" + to); // 遞歸調用：將level-1個盤子從inter移到to,from 用于周轉 moveDish(level - 1, inter, from, to); // 遞歸調用，縮小問題的規模 } } public static void main(String[] args) { int nDisks = 30; moveDish(nDisks, 'A', 'B', 'C'); }
類別三：數據的結構是按遞歸定義的
/** * Title: 遞歸求解二叉樹的深度 * Description: * @author rico * @created 2021年8月27日 下午17:5:42 */ public class BinaryTreeDepth { /** * @description 返回二叉數的深度 * @author rico * @param t * @return */ public static int getTreeDepth(Tree t) { // 樹為空 if (t == null) // 遞歸終止條件 return 0; int left = getTreeDepth(t.left); // 遞歸求左子樹深度，縮小問題的規模 int right = getTreeDepth(t.left); // 遞歸求右子樹深度，縮小問題的規模 return left > right ? left + 1 : right + 1; } }
/** * @description 前序遍歷(遞歸) * @author rico * @created 2021年8月27日 下午13:15:43 * @param root * @return */ 前序遍歷（遞歸） public String preOrder(Node
4.1 前序遍歷，非遞歸實現
起始將樹根節點添加到棧中；棧彈出一個元素，訪問該節點，并把該節點的右子節點和左子節點添加到棧中。說明，節點為空不能添加； 判斷棧是否為空，為空樹遍歷結束，不為空繼續添再加。
4.2 實例演示
// 中序遍歷，非遞歸棧實現 template
和中序遍歷非遞歸棧實現比較類似，不同的是：
中序遍歷彈出左節點之后，會繼續彈出父節點，然后判斷父節點是否有右節點，沒有繼續彈出下一個節點；有則以這個右節點進行下一次循環遍歷。
后序遍歷彈出左節點之后，繼續彈出父節點，然后判斷父節點是否有右節點，沒有繼續彈出下一個節點；有右節點且這個右節點之前已經訪問過，繼續彈出下一個節點；有右節點且這個右節點之前沒有訪問過，則以這個右節點為節點進行下一次循環遍歷。
最主要的是需要理解當一個節點的右節點已經被訪問了，則它的右節點不需要再被訪問。
將樹根節點賦值給變量 p，定義一個標記變量guard 將根節點賦值給它；循環判斷 p 是否為空，非空執行循環； 循環中將 p節點 添加到棧中，訪問 p節點 的左節點，非空就添加到棧中，繼續訪問 p節點 左節點的左節點非空就添加到棧中，直到左節點為空； 將p賦值給 guard，彈出棧頂元素將其賦值給 p，并訪問該元素； 棧不為空且彈出的棧頂元素沒有右節點或者有右節點但該右節點和 guard 相等（也就是右節點剛剛被訪問過），繼續彈出棧元素并訪問它直到，棧為空或者彈出的節點有右節點且沒有被訪問； 將最后一個彈出的節點右節點賦值給p，回到步驟二，繼續執行;
棧的變化過程
說明：在棧變化過程中的第四個棧，棧頂是D，在對D節點右訪問的時候，發現節點I已經被訪問過，此時不需要訪問D的右節點，直接輸出D節點并彈出D節點即可。
// 后序遍歷，非遞歸棧實現 template
最后小結
更加相信遞歸是種強大的技術，它使我們能夠以一種優雅而有效的方式解決許多問題。同時，它也不是解決任務問題的靈丹妙藥。由于時間或空間的限制，并不是所有的問題都可以用遞歸來解決。遞歸本身可能會帶來一些不希望看到的副作用，比如棧溢出。
有時，在解決實際問題時一看，我們并不清楚是否可以應用遞歸算法來解決問題。然而，由于遞歸的遞推性質與我們所熟悉的數學非常接近，用數學公式來推導某些關系總是有幫助的，也就是說寫出遞推關系和基本情況是使用遞歸算法的前置條件。
只要有可能，就應用記憶化。有時，在遞歸過程中，可能會出現重復計算的情況，例如斐波納契數（Fibonacci）。在這種情況下，你可以嘗試應用 記憶化技術，它將中間結果存儲在緩存中供以后重用，它可以在空間復雜性上稍加折中，從而極大地提高時間復雜性，因為它可以避免代價較高的重復計算。
當堆棧溢出時，尾遞歸可能會有所幫助。
使用遞歸實現算法通常有幾種方法。尾遞歸 是我們可以實現的遞歸的一種特殊形式。與記憶化技術不同的是，尾遞歸通過消除遞歸帶來的堆棧開銷，優化了算法的空間復雜度。更重要的是，有了尾遞歸，就可以避免經常伴隨一般遞歸而來的堆棧溢出問題，而尾遞歸的另一個優點是，與非尾遞歸相比，尾部遞歸更容易閱讀和理解。這是由于尾遞歸不存在調用后依賴（即遞歸調用是函數中的最后一個動作），這一點不同于非尾遞歸，因此，只要有可能，就應該盡量運用尾遞歸。
LNMP 二叉樹 決策樹 圖像處理 數據結構
版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。
相關文章
