往期文章（希望小伙伴們在看這篇文章之前，看一下往期文章）

（1）遞歸、搜索與回溯算法（專題零：解釋回溯算法中涉及到的名詞）【回溯算法入門必看】-CSDN博客

接下來我會用幾道題，來讓同學(xué)們利用我在專題零中提到的遞歸的宏觀思想來解決這些題目。

目錄

1. 漢諾塔

2.?合并兩個有序鏈表

3. 反轉(zhuǎn)鏈表

4. 兩兩交換鏈表中的結(jié)點

5. 快速冪

解法一? 暴力循環(huán)

解法二? 不斷拆分

解法三? 利用了二進制的特點

---

1. 漢諾塔

這道題可以說是遞歸最經(jīng)典的題目之一，接下來我們就從這道題入手，重新認(rèn)識一下遞歸是什么？

力扣題目鏈接

解析：

?

總結(jié)：我們想知道n個盤子的次數(shù)，記住了，在求解f(n)的時候，我們直接默認(rèn)f(n - 1)已經(jīng)完了就可以了！這個在前面已經(jīng)解釋過了，在此不再鰲述。我們將n-1個盤子當(dāng)作一個整體：這就是類似于分治求解子問題的思想

那么當(dāng)由3個盤子時，就有公式：f(3,x,y,z) = f(2,x,z,y),x->z,f(2,y,x,z)；當(dāng)有4個盤子時，就有公式：f(4,x,y,z) = f(3,x,z,y),x->z,f(3,y,x,z).從而推出f(n,x,y,z) = f(n,x,z,y),x->z,f(n,y,x,z)!

綜上所述：也就是說我們想移動n個盤子，就需要先移動n - 1個盤子；移動n - 1個盤子，就需要先移動n - 2個盤子 ………………；移動2個盤子，就必須先移動1個盤子；

（1）而移動1個盤子就是遞歸的終止條件

（2）而n個盤子變成n - 1個盤子就是遞歸的大問題變成小問題的方法

宏觀角度分析遞歸：

再來回顧，宏觀的細節(jié)

• 一：不要在意遞歸的細節(jié)展開圖
• 二：把遞歸的函數(shù)當(dāng)成一個“黑盒”
• 三：我們的無條件的相信“黑盒”可以為我們解決當(dāng)前的子問題（再次強調(diào)，遞歸中的每個子問題的解題步驟都是一樣）

具體構(gòu)建一個遞歸算法：

（1）創(chuàng)建函數(shù)頭 ——> 從重復(fù)子問題入手，將x柱子上的盤子，借助y柱子轉(zhuǎn)移到z柱子上。從而有函數(shù)頭為：dfs(int x,int y,int z,int n); x、y和z代表了柱子，n代表現(xiàn)在多少個盤子需要移動。x是開始柱，y是中轉(zhuǎn)柱，z是目的柱。

（2）確定函數(shù)體 ——> 無條件相信他能幫我們解決每一個子問題的。

重復(fù)的子問題如下：

• 如從 x 號柱子將n - 1個盤子借助 z 號柱子移動到 y?號柱子上
• 將 x 號柱子將最后一個盤子移動到 z?號柱子上
• 將 y?號柱子上的n - 1個盤子移動到 z?號柱子上

從而有函數(shù)體為：

① dfs(x,z,y,n - 1); ② x.back -> z; ③ dfs(y,x,z,n - 1);

（3）遞歸出口：當(dāng)剩下一個盤子的時候，也就是n == 1時。x.back -> z即可。

    //宏觀角度分析遞歸//1.創(chuàng)建函數(shù)頭//2.確定函數(shù)體，無條件相信他能幫我們解決每一個子問題的//3.遞歸出口public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {dfs(A,B,C,A.size());}public void dfs(List<Integer> x,List<Integer> y,List<Integer> z,int size){//遞歸出口if(size == 1){z.add(x.remove(x.size() - 1));return;}//封裝一個小黑盒//將x柱上的size - 1個盤子通過z柱子移動到y(tǒng)柱子上dfs(x,z,y,size - 1);//將a柱上的最后一個盤子移動到c柱子上z.add(x.remove(x.size() - 1));//將b柱上的size - 1個盤子通過a柱子移動到c柱子上dfs(y,x,z,size - 1);}

2.?合并兩個有序鏈表

力扣題目鏈接

解析：
（1）遞歸函數(shù)的含義：交給你兩個鏈表的頭結(jié)點，你幫我把它們合并起來，并且返回合并后的頭結(jié)點。
（2）函數(shù)體：選擇兩個頭結(jié)點中較?的結(jié)點作為最終合并后的頭結(jié)點，然后將剩下的鏈表交給遞歸函數(shù)去處理。
（3）遞歸出?：當(dāng)某?個鏈表為空的時候，返回另外?個鏈表。?

    // 法一：遞歸法public ListNode mergeTwoLists(ListNode l1, ListNode l2) {// 遞歸出口：當(dāng)l1或者l2為空，就返回另一個不為空的鏈表if (l1 == null)return l2;if (l2 == null)return l1;//如果l1的值小于l2，那么就讓l1作為頭結(jié)點，剩下的結(jié)點繼續(xù)比較if (l1.val <= l2.val) {l1.next = mergeTwoLists(l1.next,l2);return l1;}else{l2.next = mergeTwoLists(l1,l2.next);return l2;}}

3. 反轉(zhuǎn)鏈表

力扣題目鏈接

?

解析：?

（1）遞歸函數(shù)的含義：交給你?個鏈表的頭指針，你幫我逆序之后，返回逆序后的頭結(jié)點。
（2）函數(shù)體：先把當(dāng)前結(jié)點之后的鏈表逆序，逆序完之后，把當(dāng)前結(jié)點添加到逆序后的鏈表后?即可。（相同的子問題）
（3）遞歸出?：當(dāng)前結(jié)點為空或者當(dāng)前只有?個結(jié)點的時候，不?逆序，直接返回。

    public ListNode reverseList(ListNode head) {return dfs(head);}public ListNode dfs(ListNode h){//遞歸出口：直接到找最后一個結(jié)點，類似后序遍歷if(h == null || h.next == null){return h;}//找最后一個結(jié)點ListNode newNode = dfs(h.next);//從倒數(shù)第二個結(jié)點開始h.next.next = h;h.next = null;return newNode;}

4. 兩兩交換鏈表中的結(jié)點

力扣題目鏈接

解析：

（1）遞歸函數(shù)的含義：交給你?個鏈表，將這個鏈表兩兩交換?下，然后返回交換后的頭結(jié)點。
（2）函數(shù)體：先去處理?下第?個結(jié)點往后的鏈表，然后再把當(dāng)前的兩個結(jié)點交換?下，連接上后?處理后的鏈表。（相同的子問題）
（3）遞歸出?：當(dāng)前結(jié)點為空或者當(dāng)前只有?個結(jié)點的時候，不?交換，直接返回。?

    //后序遍歷public ListNode swapPairs(ListNode head) {//鏈表中節(jié)點的數(shù)目在范圍 [0, 100] 內(nèi)//如果只剩下一個結(jié)點就沒必要交換了，因為是兩兩交換if(head == null || head.next == null){return head;}//先去交換在我之后之后的結(jié)點ListNode newNode = swapPairs(head.next.next);ListNode ret = head.next;head.next = newNode;ret.next = head;return ret;}

?要先修改后面結(jié)點，再能修改當(dāng)前結(jié)點，很類似后序遍歷的方式。

5. 快速冪

力扣題目鏈接

解法一? 暴力循環(huán)

    public double myPow(double x, int n) {double ret = 1;int tmp = n;if(n < 0) n = -n;for(int i = 1;i <= n;i++){ret *= x;}if(tmp < 0) ret = 1.0 / ret;return ret;}

暴力循環(huán)可以解決較小的冪，當(dāng)冪的值比較大就會報超時的錯誤！！！

所以有了如下兩個改進方案：

?

解法二? 不斷拆分

（1）遞歸函數(shù)的含義：求出?x 的 n 次?是多少，然后返回。
（2）函數(shù)體：先求出 x 的?n / 2 次?是多少，然后根據(jù)?n 的奇偶，得出?x 的?n 次?是多少。
（3）遞歸出?：當(dāng)?n 為?0 的時候，返回?1 即可?。

    //第二種方法：public double myPow(double x, int n) {return n < 0 ? 1.0 / pow(x,-n) : pow(x,n);}public double pow(double x,int n){if(n == 0)return 1.0;double tmp = pow(x,n/2);return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;}

解法三? 利用了二進制的特點

例如算:

分解：

（1）而、、是倍乘關(guān)系，所以算不用11個a相乘，而是??得到，，而?得到。

（2）那么問題來了，如何將11分解成 11 = 8 + 2 + 1這樣的倍乘關(guān)系呢？

答：

（3）這里因為二進制的11中第三位為0，所以沒有?，如果跳過4呢？1011中的0，就是需要跳過的 4。

（4）

推算乘積：從低位往高位處理1011（右移一次，就把剛處理的低位移走了）

• 1011，處理末尾的1：計算a。 ；
• 1011，處理第2個1：計算。??；
• 1011，處理0：跳過。
• 1011，處理1：計算。?。

    //第三種方法：public double myPow(double x, int n) {double base = x;int tmp = n;double res = 1;if(n < 0) n = -n;while(n != 0){if((n & 1) != 0) //如果n的最后一位是1，表示這個地方需要乘res*=base;base*=base;//推算乘積，在解析有說明n>>=1;//n右移一位，把剛處理過n的最后一位去掉}if(tmp < 0) res = 1.0 / res;return res;}

注：解法三的速度比解法一快了許多，但是相比于解法二還是慢了一些，導(dǎo)致超時錯誤。

?