【演算法與資料結構 11】如何運用遞回演算法，看這一篇就夠了！

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

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

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

【演算法與資料結構 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 <iostream>
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<<Fibonacci(n);  
	return 0;
}

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

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

四、建立遞推關系

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

4.1 簡單示例：反向列印字串

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

以相反的順序列印字串，

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

遞回演算法思路：

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

• printReverse(str[1…n-1])：以相反的順序列印子字串 str[1…n-1] ，
• print(str[0])：列印字串中的第一個字符，

請注意，我們在第一步中呼叫函式本身，根據定義，它使函式遞回，下面給出代碼：

#include<iostream>
#include<stdio.h>
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;
} 

運行結果：

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

4.2 簡單示例：反轉字串

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

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

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

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

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

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

• 從輸入字串中獲取首字符和尾隨字符，即 str[0] and str[n-1]；
• 就地交換首字符和末尾字符；
• 遞回呼叫函式來反轉剩余的字串，也就是 reverseString(str[1…n-2])，

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

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

#include<iostream>
#include<string>
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<<"字串反轉后："<<s1<<endl;
	
	return 0;
}

運行結果：

可以看出，每次遞回呼叫只需要常量級的記憶體，以便交換前導和末尾字符，結果顯而易見，它滿足了問題的約束，

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