【算法與數據結構 11】遞歸算法，看這一篇就夠了！

大家好！我是【AI 菌】，一枚愛彈吉他的程序員。我熱愛AI、熱愛分享、熱愛開源！ 這博客是我對學習的一點總結與思考。如果您也對 深度學習、機器視覺、算法、Python、C++ 感興趣，可以關注我的動態，我們一起學習，一起進步~

我的博客地址為：【AI 菌】的博客

我的Github項目地址是：【AI 菌】的Github

文章目錄

一、遞歸的原理

二、遞歸的算法思想

三、建立遞推公式

四、建立遞推關系

4.1 簡單示例：反向打印字符串

4.2 簡單示例：反轉字符串

養成習慣，先贊后看！你的支持是我創作的最大動力！

我們都知道，不管是數據結構還是算法，它們的目標都是降低時間復雜度。數據結構是從數據組織形式的角度達成這個目標，而算法思維則是從數據處理的思路上去達成這個目標。

在前面的系列文章中，我們已經學習了各種數據結構的基礎知識：

【算法與數據結構 04】多圖講解——線性表、順序表、鏈表

【算法與數據結構 05】后進先出的棧——順序棧、鏈棧知多少?

【算法與數據結構 06】先進先出的隊列 —— 順序隊列 || 循環隊列 || 鏈式隊列 大盤點

【算法與數據結構 07】數組 —— 數組的基本操作( 增刪查與時間復雜度的關系！)

【算法與數據結構 08】字符串 —— 字符串匹配算法（面試高頻考點！）

【算法與數據結構 09】什么是樹、二叉樹、二叉查找樹？

【算法與數據結構 10】哈希表——高效查找的利器

從今天開始，我們將開啟算法思維的學習之路。下面，我們就來學習最常用的算法思維之一 —— 遞歸。

一、遞歸的原理

在數學與計算機科學中，遞歸 （Recursion）是指在函數的定義中使用函數自身的方法。直觀上來看，就是某個函數自己調用自己。

遞歸有兩層含義：

遞歸問題必須可以分解為若干個規模較小、與原問題形式相同的子問題。并且這些子問題可以用完全相同的解題思路來解決；

遞歸問題的演化過程是一個對原問題從大到小進行拆解的過程，并且會有一個明確的終點。最后，從這個終點開始，把小問題的答案按照原路返回，原問題便得以解決。

簡而言之，遞歸的基本思想就是把規模大的問題轉化為規模小的相同的子問題來解決

。 在函數實現時，因為大問題和小問題是一樣的問題，因此大問題的解決方法和小問題的解決方法也是同一個方法。這就產生了函數調用它自身的情況，這也正是遞歸的定義所在。

總之，遞歸的實現包含了兩個部分：

遞歸主體。是解決若干相同子問題的主要思路。

終止條件。解決問題的函數必須有明確的結束條件，否則就會導致無限遞歸的情況

二、遞歸的算法思想

遞歸的數學模型其實就是數學歸納法，這個證明方法是我們高中時期解決數列問題最常用的方法。接下來，我們通過一道題目簡單回顧一下數學歸納法。

一個常見的題目是：證明當 n 等于任意一個自然數時某命題成立。

當采用數學歸納法時，證明分為以下兩個步驟：

證明當 n = 1 時命題成立；

假設 n = m 時命題成立，那么嘗試推導出在 n = m + 1 時命題也成立。

與數學歸納法類似，當采用遞歸算法解決問題時，我們也需要圍繞這兩個步驟去做：

當你面對一個大規模問題時，如何把它分解為幾個小規模的同樣的問題；

當你把問題通過多輪分解后，最終的結果，也就是終止條件如何定義。

以上就是遞歸的算法思想。我們總結一下，寫出遞歸代碼的關鍵在于，寫出遞歸主體和找出終止條件。

對于遞歸主體，一般有兩種形式：遞推公式和遞推關系。

對于一些數學邏輯關系明顯，能用公式表達的問題，可采用遞推公式。

對于一些不易用公式表達的問題，要盡量發掘問題中的邏輯，用遞推關系表示。

三、建立遞推公式

對于一些數學邏輯關系明顯的問題，我們采用 遞推公式 + 終止條件 的方式來解決。下面以一道簡單的題目為例：

已知Fibonacci數列為：1、1、2、3、5、8…，求Fibonacci數列的第n個數是多少？

經過觀察，根據Fibonacci數列的規律，我們很容易知道：數列當前項的值等于前兩項之和。用數學公式表示為：

F ( n ) = F ( n ? 1 ) + F ( n ? 2 ) ， 其 中 F ( 1 ) = F ( 2 ) = 1 。 F(n)=F(n-1)+F(n-2)，其中F(1)=F(2)=1。 F(n)=F(n?1)+F(n?2)，其中F(1)=F(2)=1。

由此可知，當我們采用遞歸的方法來做時。遞推公式已經得到：F(n)=F(n-1)+F(n-2)；而終止條件就是：F(1)=F(2)=1。

遞推公式和終止條件都已經得出，下面就可以用代碼表示出來了：

#include using namespace std; //Fibonacci數列函數 int Fibonacci(int n) { if(n==1||n==2) return 1; else return Fibonacci(n-1)+Fibonacci(n-2); } int main() { int n=0; cin>>n; //輸出Fibonacci數列第n個數 cout<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

以上就是 遞推公式 + 終止條件 的遞歸算法思想。我們總結一下，寫出遞歸代碼的關鍵在于，寫出遞推公式和找出終止條件。

也就是說我們需要：首先找到將大問題分解成小問題的規律，并基于此寫出遞推公式；然后找出終止條件，就是當找到最簡單的問題時，如何寫出答案；最終將遞推公式和終止條件翻譯成實際代碼。

四、建立遞推關系

對于一些不易用公式表達的問題，可以盡量發掘問題中的邏輯關系，用 遞推關系+終止條件 的方式解決。

4.1 簡單示例：反向打印字符串

為了理解如何建立遞推關系，我們先從一個簡單的示例入手：

以相反的順序打印字符串。

當然，你可以使用迭代的辦法輕而易舉地解決這個問題，即從字符串的最后一個字符開始遍歷字符串。但是如何遞歸地解決它呢？

遞歸算法思路：

首先，我們可以將所需的函數定義為 printReverse(str[0…n-1])，其中 str[0] 表示字符串中的第一個字符。然后我們可以確定如下的遞推關系，分兩步完成給定的任務：

printReverse(str[1…n-1])：以相反的順序打印子字符串 str[1…n-1] 。

print(str[0])：打印字符串中的第一個字符。

請注意，我們在第一步中調用函數本身，根據定義，它使函數遞歸。下面給出代碼：

#include #include using namespace std; // 遞歸函數 void printReverse(const char *str) { // 終止條件 if (!*str) return; // 遞歸函數 printReverse(str + 1); // 打印首字符 putchar(*str); } int main() { // 初始化字符數組 char s1[] = "Hello World!"; // 調用遞歸函數 printReverse(s1); return 0; }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

運行結果：

以上就是遞推關系+終止條件的遞歸算法思想。我們總結一下，對于一些不易用公式表達的問題，寫出遞歸代碼的關鍵在于，寫出遞推關系和找出終止條件。

4.2 簡單示例：反轉字符串

為了更深一步理解遞推算法，我們在上題的基礎上，增大了難度。問題如下：

編寫一個函數，其作用是將輸入的字符串反轉過來。輸入字符串以字符數組 char[] 的形式給出。不要給另外的數組分配額外的空間，你必須原地修改輸入數組、使用 O(1) 的額外空間解決這一問題。你可以假設數組中的所有字符都是 ASCII 碼表中的可打印字符。

由于空間復雜度上的約束，因此要保證兩個連續的遞歸調用之間沒有額外的空間消耗。也就是說，我們應該把問題劃分為獨立的子問題。

因此，關于如何劃分問題的一個想法是將每個步驟中的輸入字符串減少為兩個組件：

首字符和末尾字符。

沒有首字符和末尾字符的其余子字符串。

然后我們可以獨立地解決這兩個部分。根據上述思想，我們可以提出如下遞推算法：

從輸入字符串中獲取首字符和尾隨字符，即 str[0] and str[n-1]；

就地交換首字符和末尾字符；

遞歸調用函數來反轉剩余的字符串，也就是 reverseString(str[1…n-2])。

給定輸入字符串 “hello” ，下面演示如何分解并解決它：

下面給出了上述算法的實現：

#include #include using namespace std; // 遞歸函數 void reverseString(int start, int end, string & s) { if (start >= end) { return ; } // 首尾交換 char tmp = s[start]; s[start] = s[end]; s[end] = tmp; // 遞歸函數 reverseString(start + 1, end - 1, s); } int main() { string s1 = "Hello World!"; reverseString(0, s1.size(), s1); cout<<"字符串反轉后："<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

運行結果：

可以看出，每次遞歸調用只需要常量級的內存，以便交換前導和末尾字符。結果顯而易見，它滿足了問題的約束。

養成習慣，先贊后看！你的支持是我創作的最大動力！

AI 數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。