一、遞歸

1.1 什么是遞歸？

下面是來自百度百科對遞歸算法的定義：

?遞歸是一種算法設(shè)計技術(shù)，它允許一個函數(shù)在其定義或說明中有直接或間接調(diào)用自身的方法。
?遞歸在數(shù)學(xué)和計算機(jī)科學(xué)中有著廣泛的應(yīng)用，它通過將復(fù)雜問題分解為規(guī)模較小、形式相同的子問題來求解。遞歸的基本原理包括：每一級的函數(shù)調(diào)用都有自己的變量；每一次函數(shù)調(diào)用都會有一次返回；遞歸函數(shù)中，位于遞歸調(diào)用前的語句和各級被調(diào)用函數(shù)具有相同的執(zhí)行順序；遞歸函數(shù)中，位于遞歸調(diào)用后的語句的執(zhí)行順序和各個被調(diào)用函數(shù)的順序相反；雖然每一級遞歸都有自己的變量，但是函數(shù)代碼并不會得到復(fù)制。

?簡單來說，遞歸的本質(zhì)就是函數(shù)自己調(diào)用自己！

1.2 為什么會用到遞歸？

?在回答這個問題前，我們先來看看二叉樹的先序遍歷是如何實現(xiàn)的？

?所謂先序遍歷即依次遍歷二叉樹的根節(jié)點、左子樹、右子樹。在遍歷過程中，我們發(fā)現(xiàn)左子樹和右子樹的遍歷同樣可以采用先序遍歷來實現(xiàn)。即將先序遍歷整顆二叉樹轉(zhuǎn)化先遍歷完根節(jié)點后，在先序遍歷來遍歷左子樹、右子樹。而在先序遍歷左/右子樹時，我們可以將左子樹和右子樹當(dāng)成一顆完整的二叉樹，重復(fù)上述的過程，直到為空才結(jié)束。

? 在求解問題時，我們發(fā)現(xiàn)可以將主問題可以分解為若干個相同的子問題，而這些子問題同樣都可以分解為若干個相同的子子問題，不斷重復(fù)。換句話說，假設(shè)我們可以通過一個方法f（可以將f想象成數(shù)學(xué)中求解問題的函數(shù)表達(dá)式f(x)）來求解主問題，而主問題所轉(zhuǎn)化出的子問題同樣可以通過方法f來解決（而子問題所衍生出的子子問題同樣可以通過方法f來解決，不斷重復(fù)下去），從而實現(xiàn)函數(shù)自己調(diào)用自己！當(dāng)面臨這種情況時，即可使用遞歸算法來解決問題。

1.3 如何快速編寫正確的遞歸代碼？

1. 找到相同的子問題，該過程決定了函數(shù)頭的設(shè)計（即函數(shù)參數(shù)需要傳哪些）
2. 將其中一個子問題進(jìn)行分析，在此過程中將遞歸函數(shù)當(dāng)作一個黑盒，該函數(shù)能完成我們所賦予的功能。該過程決定了函數(shù)的函數(shù)體。
3. 最后當(dāng)然是返回值了。在何種情況下，遞歸結(jié)束。

下面以二叉樹的先序遍歷為例進(jìn)行分析：
? 首先先序遍歷過程：根、左子樹、右子樹。而左子樹和右子樹顯然是一個相同的子問題（左子樹和右子樹還可以繼續(xù)細(xì)分下去，都行相同子問題，就不多說了）。所有我們需要給函數(shù)傳一個根節(jié)點參數(shù)，用于分割整顆二叉樹。

void TreePrev(TreeNode* root)//函數(shù)頭

? 現(xiàn)在我們賦予了該遞歸函數(shù)功能：先序遍歷二叉樹?，F(xiàn)在我們?nèi)∑渲幸粋€子問題進(jìn)行分析，首先我們需要遍歷根節(jié)點，然后可以通過該遞歸函數(shù)來實現(xiàn)左子樹、右子樹的先序遍歷了，即：

cout << root -> val <<" ";//根節(jié)點
//我們賦予了函數(shù)TreePrev先序遍歷二叉樹的功能，所有我們可以把該函數(shù)當(dāng)作一個黑盒。
//只要我們將二叉樹的根節(jié)點傳入該黑盒，便可實現(xiàn)這顆二叉樹的先序遍歷。（實際該過程可以由畫遞歸展開圖驗證，由于篇幅問題博主就不多說了）
TreePrev(root -> left);//遍歷左子樹
TreePrev(root -> right);//遍歷右子樹

? 最后就是遞歸什么時候結(jié)束了。顯然當(dāng)根節(jié)點未空指針時，遞歸結(jié)束。此時返回空即可

if(root == nullptr)
	return;

所以整體代碼就是：

void TreePrev(TreeNode* root)//函數(shù)頭
{
	if(root == nullptr)
		return;
	cout << root -> val <<" ";//根節(jié)點
	//我們賦予了函數(shù)TreePrev先序遍歷二叉樹的功能，所有我們可以把該函數(shù)當(dāng)作一個黑盒。
	//只要我們將二叉樹的根節(jié)點傳入該黑盒，便可實現(xiàn)這顆二叉樹的先序遍歷。（實際該過程可以由畫遞歸展開圖驗證，由于篇幅問題博主就不多說了）
	TreePrev(root -> left);//遍歷左子樹
	TreePrev(root -> right);//遍歷右子樹	
}

二、力扣相關(guān)筆試題解析

面試題 08.06. 漢諾塔問題

【分析】：
?題目指讓A柱子中的N個圓盤（自下而上降序）借助B轉(zhuǎn)移到C柱子上，并且保存順序不變。所以我們可以考慮將A柱子上的后N-1個圓盤當(dāng)作一個整體移到B上，然后將A中剩余的最后一個圓盤移到C上；最后在將B盤上的所有圓盤當(dāng)作一個整體移到C上即可達(dá)成目的！
?在題目的分析過程中，出現(xiàn)將A上的N-1個圓盤移到B上，將B上的N-1個圓盤移到C上的過程。而這兩個步驟顯然是一個遞歸子問題（將一個柱子上的N個圓盤，借助另一個柱子轉(zhuǎn)移到第三個柱子）。由于該過程中是具體圓盤在3根柱子間的移到，所以函數(shù)頭因有4個參數(shù)：柱A、柱B、柱C、移到圓盤個數(shù)??！

?由于該過程中，我們通過遞歸函數(shù)（黑盒）將A柱上的N-1個圓盤移到B柱上、將A柱上的剩余的最后一個圓盤移到C柱、通過遞歸函數(shù)（黑盒）將B中的所有圓盤移到C柱。所以函數(shù)體為：

//_hanota為我們待實現(xiàn)的遞歸函數(shù)，該函數(shù)的功能是將將一個柱子上的N個圓盤，借助另一個柱子轉(zhuǎn)移到第三個柱子
//所以將該函數(shù)想成一個黑盒，只需向該函數(shù)傳遞正確參數(shù)，即可實現(xiàn)對應(yīng)的功能?。ň唧w由函數(shù)展開圖證明）
//先將A中前num-1個圓盤借助C移到B
_hanota(A, C, B, num - 1);
//將A剩余的最后一個元素移到C柱子
C.push_back(A.back());
A.pop_back();
//將B上的num-1個圓盤借助A移到C柱子上
_hanota(B, A, C, num - 1);

?最后返回值就不多說了，A中只有一個圓盤時，無需解決B，直接將圓盤從A移到C上。

【下面是其中一個子問題的圓盤轉(zhuǎn)移過程圖解】：

【代碼編寫】：

class Solution {
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        _hanota(A, B, C, A.size());
    }
    void _hanota(vector<int>& A, vector<int>& B, vector<int>& C, int num) 
    {
        if(num == 1)
        {
            C.push_back(A.back());
            A.pop_back();
            return;
        }
        //先將A中前num-1個圓盤借助C移到B
        _hanota(A, C, B, num - 1);
        //將A剩余的最后一個元素移到C柱子
        C.push_back(A.back());
        A.pop_back();
        //將B上的num-1個圓盤借助A移到C柱子上
        _hanota(B, A, C, num - 1);
    }
};

21. 合并兩個有序鏈表

【題目】：

【解析】：
?這道題目的就是將兩個升序的鏈表合并成一個升序鏈表，并返回新鏈表的頭節(jié)點。
?在本題中，我們可以先選出兩鏈表中節(jié)點值較小的節(jié)點，然后想辦法將該鏈表中剩下的節(jié)點和另一條鏈表合并為升序鏈表；最后將最開始選出的較小節(jié)點的next指向該新合并的新節(jié)點即可解決問題。顯然將該鏈表中剩下的節(jié)點和另一條鏈表合并為升序鏈表就是一個遞歸子問題，所以可以采用遞歸方式解決問題。
?由于遞歸子問題是合并兩個有序鏈表，所有函數(shù)頭傳的參數(shù)為待合并的兩個鏈表頭節(jié)點。至于函數(shù)體，我們只需挑選出原來兩鏈表中頭節(jié)點值較小的節(jié)點作為新鏈表的頭節(jié)點，然后通過遞歸函數(shù)將剩下的元素和另一個鏈表合并，最后將新鏈表的頭節(jié)點的next指向合并鏈表的頭節(jié)點。當(dāng)鏈表節(jié)點為空時，遞歸結(jié)束。

【代碼解析】：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    	//特殊處理
        if (list1 == nullptr)
            return list2;
        if (list2 == nullptr)
            return list1;
         
        if (list1->val < list2->val)
        {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
        else
        {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};

LCR 024. 反轉(zhuǎn)鏈表

反轉(zhuǎn)鏈表我們可以將后n-1個節(jié)點反轉(zhuǎn)（并返回反轉(zhuǎn)后鏈表的頭節(jié)點），然后在將原鏈表的頭結(jié)合和新鏈表鏈接即可。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr || head->next == nullptr)
            return head;
        ListNode* newhead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newhead;
    }
}

24. 兩兩交換鏈表中的節(jié)點

這道題本質(zhì)上和反轉(zhuǎn)鏈表類似，我們可以先將原鏈表頭兩個節(jié)點反轉(zhuǎn)，然后利用遞歸子問題將后續(xù)所有節(jié)點當(dāng)成一個完成鏈表，完成兩兩交換鏈表中的節(jié)點。最后將交換后的鏈表和原鏈表的頭兩個數(shù)據(jù)鏈接即可。（如果鏈表為空，或只有一個元素，則遞歸結(jié)束）

文章來源地址http://www.zghlxwxcb.cn/news/detail-845252.html

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr)
            return head;
        ListNode* newhead = head->next;
        head->next = swapPairs(newhead->next);
        newhead->next = head;
        return newhead;
    }
};

到了這里，關(guān)于遞歸究竟是什么？如何快速編寫正確的遞歸代碼？ —— 力扣經(jīng)典面試題詳解的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！