目錄

1.什么是遞歸

1.1二叉樹的遍歷

1.2快速排序

1.3歸并排序

2.為什么會用到遞歸

3.如何理解遞歸

4.如何寫好一個遞歸

5.什么是搜索

5.1深度（dfs）優(yōu)先遍歷&優(yōu)先搜索

5.2寬度（bfs）優(yōu)先遍歷&優(yōu)先搜索

6.回溯

---

1.什么是遞歸

我們呢下面介紹一下遞歸的幾個使用的場景，這個里面不會介紹像這個斐波那契數(shù)列那樣的遞歸（就是數(shù)學(xué)函數(shù)，很容易理解），我們就拿數(shù)據(jù)結(jié)構(gòu)里面的排序算法和二叉樹的遍歷作為例子熟悉一下這個過程

1.1二叉樹的遍歷

我們這個地方是以后序遍歷作為例子。對于一個二叉樹而言，這個后序遍歷的時候我們先遍歷根節(jié)點的左子樹，再去遍歷根節(jié)點的右子樹。最后遍歷這個根節(jié)點；

在遍歷左子樹的時候，我們要先遍歷這個左子樹的根節(jié)點的左子樹，再去遍歷這個左子樹根節(jié)點的右子樹，以此類推，對于任何一個子樹，我們都會先遍歷這個根節(jié)點的左子樹，再去遍歷這個根節(jié)點的右子樹；

1.2快速排序

快速排序和下面介紹的這個歸并排序?qū)τ诔鯇W(xué)者而言很相似（我就是這個感覺），但是兩個排序算法還是有很多的差異的；

快速排序之所以敢這么叫這個名字，自身的這個時間消耗上面肯定是可以的，它是有使用價值的，并不想其他的一些排序算法只有教學(xué)意義，沒有實踐意義；

快排需要先確定一個基準元素，把小于這個元素的放到左邊，大于這個元素的放到右邊，分別對于這個左邊的和右邊的進行排序，還是選擇基準元素，按照上面的方法進行下去；

1.3歸并排序

歸并排序就和上面的快速排序有點不同了，因為歸并排序是直接從中間分開，然后再把這個自己左右分開，直到分成一個一個的元素，最后把這個元素有序的組合起來即可；

下面的這個就是歸并排序的過程展示：就是分開之后合并的過程，這個合并的時候我們是使用的雙指針的方法合并的（通過指針的移動）；

2.為什么會用到遞歸

我們在解決一個問題的時候，把這個問題分解為諸多的子問題，可以使用一個方法解決這個主問題，但是解決子問題的時候同樣可以使用這個方法解決；

3.如何理解遞歸

3.1遞歸展開細節(jié)圖：這個是初學(xué)的時候，老師經(jīng)常搞的一種方法，但是這個并不一定會簡化我們對于這個遞歸問題的理解；

3.2二叉樹的題目：我們在二叉樹學(xué)習(xí)的時候，尤其是涉及到這個二叉樹的遍歷，因為二叉樹的遍歷里面遍歷任何一個子樹的方法都是一樣的，他們都是若干個子問題，我們就可以直接使用遞歸解決這個問題；

3.3宏觀看待遞歸過程：我們跳出上面的遞歸細節(jié)展開圖，找準子問題，只需要關(guān)注一個問題的實現(xiàn)，再去套用這個方法解決其他的問題；

下面我們按照這個思路簡單的寫一下dfs（深度遍歷）和歸并的偽代碼：

我們沒有實現(xiàn)，但是我們先把這個root->left作為函數(shù)的參數(shù)，root->right作為函數(shù)的參數(shù)，最后判斷這個結(jié)束條件（到達葉子結(jié)點就結(jié)束）；

void dfs(treenode* root)
{//結(jié)束條件：遇到葉子結(jié)點if (root == NULL){return;}dfs(root->left);dfs(root->right);printf("%d", root->val);
}

我們先計算這個mid值大小，再把這個mid作為參數(shù)傳遞進去，分別傳遞這個左邊區(qū)間，和右邊區(qū)間，使用這個函數(shù)進行排序，最后合并兩個有序數(shù)組，結(jié)束條件就是left>=right,結(jié)束遞歸的過程；

void merge(int* nums, int left, int right)
{//遞歸結(jié)束的出口if (left >= right){return;}int mid = (left + right) / 2;merge(nums, left, mid);merge(nums, mid + 1,right);//合并兩個有序數(shù)組
}

4.如何寫好一個遞歸

4.1函數(shù)頭的書寫：找到一個主問題里面的字問題，看看是否可以使用相同的方法解決子問題；

4.2函數(shù)體的書寫：只關(guān)注某一個子問題，來進行函數(shù)體的實現(xiàn)；

4.3結(jié)束條件：找這個遞歸的出口，作為結(jié)束遞歸的條件；

5.什么是搜索

5.1深度（dfs）優(yōu)先遍歷&優(yōu)先搜索

深度就是一條路走到盡頭之后再去折返回去，這個里面遍歷只是過程的一種形式，搜索才是真正想要達到的目的；

5.2寬度（bfs）優(yōu)先遍歷&優(yōu)先搜索

寬度就是你一層一層的進行，按照這個二叉樹的層狀結(jié)構(gòu)進行遍歷，這一層結(jié)束之后進行下一層；

6.回溯

回溯就是深度搜索，我們可以舉例一下這個走迷宮的問題幫助我們理解一下，當(dāng)我們走到一個迷宮的某一個節(jié)點的時候，我們有多個選擇，我們肯定是只能走其中的一條，這個時候，我們認準一條路并且總下去，這個時候，我們發(fā)現(xiàn)走到了死胡同，這個時候我們就需要則返回那個岔路口，這個從現(xiàn)在所在位置返回到剛剛做選擇的岔路口就是一個回溯的過程，因此我們說這個回溯和深度搜索沒有什么本質(zhì)的區(qū)別，都是一條路走到黑再去選擇另外的一條路，僅此而已。