Hi，你好，今天的文章主要是從宏觀角度聊聊遞歸這種算法思想，文章主要內(nèi)容如下：
01
通過(guò)數(shù)組求和看遞歸的基本性質(zhì)
現(xiàn)在給出一個(gè)數(shù)組arr={1,3,6}，問(wèn)如何用遞歸方式求出數(shù)組中所有元素的總和。假設(shè)現(xiàn)在A拿到了這個(gè)問(wèn)題，但是A只能計(jì)算數(shù)組中的第一個(gè)元素值和剩余元素總和的和，那這時(shí)怎么辦呢？A就想，我可以先把數(shù)組中第一個(gè)元素1的值記錄下來(lái)，然后讓B計(jì)算數(shù)組中剩余元素的總和。于是，B就收到一個(gè)任務(wù)，需要計(jì)算數(shù)組{3,6}的總和，同樣的B和A一樣也只能計(jì)算數(shù)組中的第一個(gè)元素值和剩余元素總和的和。因此，B記錄下他拿到的數(shù)組中的第一個(gè)元素3的值，然后讓C去計(jì)算數(shù)組中剩余元素的總和。這時(shí)，C收到一個(gè)任務(wù)，是計(jì)算數(shù)組{6}的總和，同樣的C和A一樣也只能計(jì)算數(shù)組中的第一個(gè)元素值和剩余元素總和的和，并且除了第一個(gè)元素外，C不知道數(shù)組中還剩余哪些元素。于是，C將數(shù)組中的第一個(gè)元素6的值記錄下來(lái)，然后讓D去計(jì)算數(shù)組中剩余元素的總和。D在收到任務(wù)后，一看數(shù)組是空的，就知道數(shù)組中元素總和是0。然后D就告訴C，剩余元素的總和是0。于是C將自己記錄的元素6和D告訴他的剩余元素的總和0相加后得到6，他就把這個(gè)結(jié)果告訴了B。
B在收到C的結(jié)果6后，同樣的將自己記錄的元素3和其相加得到9，于是他就把這個(gè)結(jié)果告訴了A。A在拿到B告訴他的結(jié)果9后，將其和自己記錄的元素1相加得到結(jié)果10。這時(shí)A就知道數(shù)組中所有元素的總和是10。上述過(guò)程中A拿到求數(shù)組中所有元素和這個(gè)問(wèn)題后，將其告訴B，B再告訴C，C再告訴D，這個(gè)過(guò)程我們可以稱之為”遞“。然后，D將結(jié)果告訴C，C再告訴B，B在告訴A的這個(gè)過(guò)程我們可以稱之為”歸“。在上述問(wèn)題的描述中，其實(shí)就包含了遞歸這種算法思想的一些基本條件：一是一個(gè)問(wèn)題可以分解為多個(gè)更小的子問(wèn)題并且這多個(gè)更小的子問(wèn)題的求解思路完全一樣對(duì)于數(shù)組求和這個(gè)問(wèn)題來(lái)說(shuō)，A要知道自己拿到的數(shù)組的總和這個(gè)問(wèn)題，可以分解為B要知道除去數(shù)組第一個(gè)元素外剩余元素總和這樣一個(gè)問(wèn)題。同時(shí)，對(duì)于A和B來(lái)說(shuō)，他們求解問(wèn)題的思路是一樣的，即只計(jì)算自己拿到的數(shù)組中第一個(gè)元素值和數(shù)組中剩余元素總和的和，而不管數(shù)組中剩余元素總和的和是如何計(jì)算的。二是存在一個(gè)終止條件，可以讓遞歸停下來(lái)。比如數(shù)組求和的終止條件就是數(shù)組中沒(méi)有剩余元素需要計(jì)算了。遞歸代碼的編寫(xiě)一是要知道遞歸終止條件，對(duì)于數(shù)組求和這個(gè)問(wèn)題來(lái)說(shuō)，其終止條件是數(shù)組中沒(méi)有元素需要計(jì)算了，代碼表示是：// begin 表示從數(shù)組中哪個(gè)索引位置開(kāi)始// 當(dāng)begin == arr.length表示數(shù)組中沒(méi)有剩余元素if (begin == arr.length) { return 0;}
二是要知道遞歸遞推公式，就數(shù)組求和這個(gè)問(wèn)題來(lái)說(shuō)，遞推公式是:
arr[begin] + sum(begin + 1, arr);
有了終止條件和遞推公式，就可以寫(xiě)出遞歸求解數(shù)組中所有元素和的代碼了，實(shí)現(xiàn)如下：
public int sum (int[] arr) { return sum(0, arr);}
private int sum(int begin, int[] arr) { if (begin == arr.length) { return 0; }
return arr[begin] + sum(begin + 1, arr); }
這里我們?cè)诘?行sum(int begin, int[] arr)這個(gè)方法中調(diào)用了sum(int begin, int[] arr)方法它自己，即16行的sum(begin + 1, arr)，這一點(diǎn)可能會(huì)讓你覺(jué)得困惑。
我們可以這樣理解，方法sum(int begin, int[] arr)是計(jì)算數(shù)組中從索引begin開(kāi)始所有元素的總和，而該方法的計(jì)算規(guī)則是我計(jì)算的是當(dāng)前數(shù)組起始位置begin所對(duì)應(yīng)的元素值和數(shù)組中剩余元素的總和的和。那么，我就需要有個(gè)方法可以告訴我數(shù)組中剩余元素的總和是多少。
這時(shí)，剛好有個(gè)方法fun(int begin, int[] arr)，只要我告訴它數(shù)組是什么樣的，以及從哪個(gè)索引位置開(kāi)始計(jì)算，它就會(huì)告訴我數(shù)組中剩余元素的總和。只不過(guò)這個(gè)方法fun(int begin, int[] arr)所需的參數(shù)和我自己一樣而已。于是，在代碼中看起來(lái)就是方法sum(int begin, int[] arr)調(diào)用了它自己。
02
鏈表的天然遞歸性
接著我們看下如何用遞歸思想解答LeetCode中#203.移除鏈表元素這個(gè)問(wèn)題。
題目描述：
刪除鏈表中等于給定值 val 的所有節(jié)點(diǎn)。
示例:
輸入: 1->2->6->3->4->5->6, val = 6
輸出: 1->2->3->4->5
為了方便演示，我將題目示例中給定的鏈表進(jìn)行了簡(jiǎn)化。如下圖：
先看下”遞“的過(guò)程，對(duì)于A來(lái)說(shuō)，他在拿到給定的鏈表后，記錄下了頭節(jié)點(diǎn)，然后將頭結(jié)點(diǎn)之后的鏈表給了B。
同樣的B在拿到給定的鏈表后，記錄下了頭節(jié)點(diǎn)，然后將頭結(jié)點(diǎn)之后的鏈表給了C。C在拿到給定的鏈表后，記錄下了頭節(jié)點(diǎn)，然后將頭結(jié)點(diǎn)之后的鏈表給了D。D在拿到給定的鏈表后，記錄下了頭節(jié)點(diǎn)，然后將頭結(jié)點(diǎn)之后的鏈表給了E。E拿到空鏈表之后，就將其返回給了D，這時(shí)D就知道它的鏈表是3—>null。D將自己得到的結(jié)果3—>null返回給了C，這時(shí)C就知道它的鏈表是6—>3—>null。接著C需要將自己計(jì)算的結(jié)果返回給B，但這時(shí)C發(fā)現(xiàn)自己拿的鏈表的頭結(jié)點(diǎn)是和要移除的元素val=6相等的，因此C返回B的結(jié)果應(yīng)該是去掉頭結(jié)點(diǎn)6后的剩余部分3—>null。B在拿到C返回的結(jié)果后，就知道它的鏈表是2—>3—>null。然后，它將這個(gè)結(jié)果告訴了A。A在拿到B返回的結(jié)果后，就知道它的鏈表是1—>2—>3—>null，也就是移除鏈表中元素val=6之后的結(jié)果。對(duì)于上述的遞歸過(guò)程，可以簡(jiǎn)化為兩個(gè)步驟：一是記錄下鏈表當(dāng)前頭結(jié)點(diǎn)head，然后調(diào)用移除鏈表中結(jié)點(diǎn)值val=6的方法；二是在拿到調(diào)用方法之后的結(jié)果時(shí)，判斷一下當(dāng)前記錄的頭結(jié)點(diǎn)的值是不是等于val=6，如果不等，則將調(diào)用方法之后的結(jié)果掛在所記錄的頭結(jié)點(diǎn)之后，返回；如果相等，則直接將調(diào)用方法之后的結(jié)果返回。
鏈表這種數(shù)據(jù)結(jié)構(gòu)，我們說(shuō)它具有天然遞歸性，就在于對(duì)于一個(gè)鏈表，我們可以將其分解為頭結(jié)點(diǎn)和一個(gè)子鏈表。然后，對(duì)于子鏈表同樣可以分解為一個(gè)頭結(jié)點(diǎn)和一個(gè)子鏈表。這滿足的是遞歸思想中的：一個(gè)問(wèn)題可以分解為多個(gè)子問(wèn)題并且這多個(gè)子問(wèn)題求解思路是一樣的這一條件。此外，對(duì)于鏈表分解到最后時(shí)，頭結(jié)點(diǎn)為null，這滿足的是遞歸思想中的：存在遞歸終止條件，讓遞歸停下來(lái)這一條件。
public ListNode removeElements(ListNode head, int val) { if (head == null) { return null; }
ListNode result = removeElements(head.next, val);
if (head.val == val) { return result; } else { head.next = result; return head; }}
題圖：stux / Pixabay
