【算法】遞歸的藝術：從本質思想到遞歸樹，深入剖析算法的性能權衡詳情 - C語言,算法,遞歸,C,C++,後端開發,yyds乾貨盤點蒙奇D索隆博客

(遞歸)

導讀

大家好，很高興又和大家見面啦！！！在上一篇內容中，我們揭開了遞歸的"神秘面紗"：遞歸就是函數自己調用自己，並且掌握了它的兩個必要條件：

必須有一個明確的結束條件
每次遞歸調用都要向結束條件靠近

理解了這些基礎知識後，不知道你是否也曾思考過這樣的問題：

為什麼我們需要遞歸？如果所有問題都能用循環解決，遞歸存在的意義是什麼？
遞歸到底有什麼魔力，讓程序員們對它又愛又恨？為什麼有人説"遞歸讓代碼更優雅"，卻又警告"小心棧溢出"？
當你面對一個複雜問題時，如何判斷它是否適合用遞歸解決？遞歸是如何將複雜問題"化繁為簡"的？
更重要的是，遞歸的執行過程到底是怎樣的？函數一次次調用自己時，計算機內部發生了什麼？

如果你對這些問題感到好奇，那麼今天的探討將為你一一揭曉答案。讓我們繼續深入遞歸的世界，探索其背後的精妙之處！

一、核心思想

遞歸的核心思想：分而治之 遞歸的本質是將一個大規模問題分解成一個或幾個規模較小、但與原問題本質相同的小問題。這些小問題再用同樣的方法繼續分解，直到分解到足夠小、可以直接解決（這個“足夠小”的點就是遞歸基）。

二、適用場景

遞歸這種分解思想非常適用於以下場景：

問題的定義本身就是遞歸的場景：
- 斐波那契數列：$F(n) = F(n - 1) + F(n - 2)$
- 階乘：$n! = n * (n - 1)!$
操作的數據結構是遞歸的場景：
- 樹的相關操作：遍歷、搜索、計算深度、計算結點數量……
- 鏈表：將長度為 $n$ 的鏈表 = $1$ 個結點 + 長度為 $(n - 1)$ 的鏈表
- 圖的深度優先遍歷
需要回溯算法的問題：
- 迷宮問題：走到一個岔路口，先嚐試一條路走到底（遞歸），如果走不通，就返回到上一個岔路口（回溯），再嘗試另一條路
- 八皇后問題：嘗試在棋盤上放置一個皇后，然後遞歸地在下一行放置，如果導致衝突，就撤銷當前選擇（回溯），嘗試下一個位置

三、遞歸與迭代

之前我們有介紹過遞歸與迭代的區別：

因為計算機內存的限制，遞歸會隨着層次的深入，耗盡內存空間，進而出現 棧溢出 的情況導致遞歸的結束；
但是迭代是直接在內存空間中申請一塊空間，並在這個空間中進行一系列的操作，如果不加以限制，則會出現死循環；

這是二者在限制條件下的區別，簡單的説：

遞歸無限制條件（即遞歸結束條件）時，會出現棧溢出而導致遞歸的終止；
迭代無限制條件（即循環結束條件）時，會出現死循環

但是二者的區別不限於此，二者在實現的細節上也存在很大的區別：

遞歸只需要關注 遞歸基 的具體實現，而其它的步驟則會簡化為函數的調用；
迭代則會明確整個過程的每一個細節

四、優勢與缺點

4.1 優勢

遞歸的優勢可以總結為兩點：

代碼簡潔、清晰：對於適用的問題，遞歸代碼通常比等價的循環代碼要簡短的多，可讀性更強，它更加接近我們對問題的數學或邏輯定義；
簡化複雜問題：它將包含多重循環、狀態維護的複雜邏輯，簡化成幾個簡單的遞歸調用；

這裏我們以斐波那契數列的實現來具體説明其優勢：

//斐波那契數列——遞歸實現
int Fbn(int n) {
	if (n == 0) {
		return 0;
	}
	if (n == 1) {
		return 1;
	}
	return Fbn(n - 1) + Fbn(n - 2);
}

//斐波那契數列——迭代實現
int Fbn_(int n) {
	if (n == 0) {
		return 0;
	}
	if (n == 1) {
		return 1;
	}
	int a = 0, b = 1, c = 0;
	for (int i = 2; i <= n; i++) {
		c = a + b;
		a = b;
		b = c;
	}
	return c;
}

上述的代碼片段分別展示了斐波那契數列的遞歸實現與迭代實現這兩種實現方式，下面我們先來看一下兩個函數的測試結果：

斐波那契數列.png

可以看到，在計算斐波那契數列時，遞歸在整個過程中只用關心某一項是如何計算，如我們要計算 $F(5)$ 我們只需要知道它的值可以通過 $F(4) + F(3)$ 獲取，但是具體如何獲取的我們不需要過多關注；而迭代的實現中，我們則需要計算從 $F(2)$ 到 $F(5)$ 的每一項的值，進而得到 $F(5)$ 的值；相比於迭代，遞歸在代碼的編寫上會更加的簡潔，並且遞歸將迭代中的具體實現邏輯簡化為了斐波那契數列的遞推公式；

4.2 缺點

但是遞歸同樣也會有一些不可忽視的缺點：

性能開銷大

因為遞歸是直接在內存空間中申請新的函數棧幀來實現每一次遞歸基，所以當遞歸的深度增加，對函數棧幀的需求也會增加，當申請的函數棧幀到達內存極限時，繼續申請函數棧幀，就會導致 棧溢出。

可能產生重複計算

遞歸的實現是關注於 遞歸基 的實現細節，就比如計算斐波那契數列時，我們只需要關注其遞歸基 $F(0)$ 與 $F(1)$，而其它的數值對應的斐波那契數我們則可以通過遞推公式進行推導，如：

$F(5) = F(4) + F(3)$
$F(4) = F(3) + F(2)$
$F(3) = F(2) + F(1)$
$F(2) = F(1) + F(0)$

可以看到，在整個的推導過程中，當我們要計算 $F(5)$ 的斐波那契數時，我們需要在 $F(5)$ 的遞推式中計算一次 $F(3)$ ，在 $F(4)$ 的遞推式中計算一次 $F(3)$ ；也就是説在計算 $F(5)$ 的過程中，對於 $F(3)$ 這個數的值，我們就重複計算了兩次；

難以調試

由於遞歸的代碼過於簡潔，將複雜的實現邏輯簡化為了相應的函數調用，因此在具體的調試過程中會增加整體的調試難度；

4.3 小結

綜上所述，遞歸作為一種強大的編程工具，它可以用於解決特定類型問題，而不能作為盲目替代迭代的通用工具；當一個複雜的問題可以通過分而治之的思想將其分解為相同類型的子問題時，我們可以優先考慮使用遞歸實現；而當我們需要關注算法的性能，或者使用遞歸時其遞歸深度可能會導致棧溢出的問題時，使用迭代通常是更安全、更高效的選擇。現在我們已經解決了第一個問題——為什麼要使用遞歸？那我們又應該如何使用遞歸呢？下面我們就來了解以下實現遞歸的具體步驟；

五、實現步驟

當我們要通過遞歸解決一個複雜的問題時，我們可以將其劃分為 $4$ 個具體步驟：

定義遞歸函數
尋找遞歸基
尋找遞進關係
組合與優化

接下來我們就通過階乘的計算來具體瞭解一下這 $4$ 個步驟；

5.1 定義遞歸函數

當我們要通過遞歸解決 階乘問題 時，我們需要明確函數的三要素——函數名、函數參數以及函數的返回類型；

函數名：我們可以直接通過階乘的英文翻譯：$Factorial$ 來進行命名；
函數參數：因為階乘計算的是整型值，因此我們可以根據任務的規模大小來定義函數的參數：
- 數值的大小不超過 int 的最大值 INT_MAX ，我們可以定義其參數類型為 int；
- 數值的大小超過 int 的最大值 INT_MAX ，則我們需要使用 long long 來作為參數類型；
函數返回類型：函數的返回類型需要根據其值的大小來進行確定：
- 當值的大小不超過 INT_MAX 時，函數的返回類型可以定義為 int
- 當值的大小超過 INT_MAX 時，函數的返回類型可以定義為 long long

這裏我們就以 int 型為例，來定義遞歸函數：

int Factorial(int n) {

}

5.2 尋找遞歸基

遞歸基 指的就是 遞歸出口 ，也就是在整個遞歸的過程中 最簡單、不需要通過遞歸就能得到答案的情況。而在 階乘問題 中，其遞歸基為 $0! = 1$ 與 $1! = 1$ ，因此該問題的遞歸實現中，其函數出口我們可以定義為：

if (n == 0 || n == 1) {
	return 1;
}

5.3 尋找遞進關係

遞進關係 我們可以理解為 遞推公式 ，這是實現遞歸的引擎。我們要尋找一個問題的 遞進關係 ，我們就需要通過 分而治之 的思想，將該問題分解為規模更小、但結構相同的子問題：

斐波那契數列 的遞推公式為：$F(n) = F(n - 1) + F(n - 2)$
階乘問題的遞推公式為：$n! = n * (n - 1)!$

因此根據該 遞推公式 我們可以得到函數的 遞進關係：

return n * Factorial(n - 1);

5.4 組合與優化

在確保了遞歸調用始終是靠近 遞歸基 後，我們就可以將所有內容加以整合並對其進行優化，得到最終的 階乘問題 的 遞歸實現 代碼：

//階乘問題
int Factorial(int n) {
	if (n == 0 || n == 1) {
		return 1;
	}
	return n * Factorial(n - 1);
}

説明這麼多，那麼遞歸算法具體是如何實現的呢？它的算法執行過程是怎麼樣的？要了解遞歸算法的具體實現過程，我們就需要藉助一個工具——遞歸樹；

六、遞歸樹

遞歸樹：一種用於分析和可視化遞歸算法執行過程的樹形結構。它是理解遞歸工作原理、分析遞歸算法時間複雜度的強大工具。這裏我們以 階乘問題 的遞歸算法為例：

flowchart TB
a[5!]--->b[5]
a--->c[4!]
c--->d[4]
c--->e[3!]
e--->f[3]
e--->g[2!]
g--->h[2]
g--->i[1!]
i--->j[1! == 1]

在上面這棵二叉樹中，其左子樹為所求值 $n$ ，其右子樹則為該算法的遞歸函數 $f(n - 1)$。也就是説，當我們要計算 $5!$ ，其遞歸算法的執行過程會根據右子樹不斷的進行深入，直到遞歸函數到達 遞歸基 ，函數才會開始迴歸：

flowchart BT
a[120]
b[5]
c[24]
d[4]
e[6]
f[3]
g[2]
h[2]
i[1]
j[1! == 1]
j--->i
h--->g
i--->g
f--->e
g--->e
d--->c
e--->c
b--->a
c--->a

最終遞歸函數會將該 遞歸樹 的根節點中存儲的值進行返回。當我們要對該算法進行分析時，我們實際分析的是該棵遞歸樹的高度與 結點數量：

第一層：$C(1) = 1$
第二層：$C(2) = 2$
第三層：$C(3) = 2$
$\cdots$
第n層：$C(n) = 1$

在這些結點中，我們需要關注每個結點的具體 工作量 ：

第一層：根結點的工作量為 $O(1)$ ，即該結點執行了一次 函數調用
第二層：
- 左子樹的工作量為 $O(1)$ ，即該結點執行了一次數乘
- 右子樹的工作量為 $O(1)$ ，即該結點執行了一次 函數調用
$\cdots$
第 $n$ 層：該結點的工作量為 $O(1)$ ，即該結點執行了一次 賦值返回

在計算 $n!$ 的函數遞歸中，其對應的遞歸樹中除了第一層與第 $n$ 層只有 $1$ 個結點外，其它層均有 $2$ 個結點，即整棵樹的結點總數為：

$C(n) = 1 + \underbrace{2 + 2 + \cdots + 2}_{n - 2\text{個}2} + 1 = 2 + 2 * (n - 2) = 2 * (n - 1)$

該算法的時間複雜度我們可以通過下面的公式計算得出：

$$O(N) = 結點數量（C(N)）* 結點工作量（O(N)）$$

即：

$$ \begin{align*} O(N) &= C(N) * O(N) \ &= 2 * (n - 1) * O(1) \ &= O(2n) - O(2) \ &= O(n) \rightarrow O(N) \end{align*} $$

也就是説，通過遞歸算法計算 階乘問題 ，其算法的時間複雜度為：$O(N)$ 。該算法的空間複雜度分析則由遞歸的深度決定，即通過樹的深度決定：

階乘問題 中，其對應的遞歸樹的深度為 $n$
每一層遞歸我們都需要在內存中開闢大小為 $O(1)$ 的函數棧幀空間
算法的空間複雜度為 $O(N) = n * O(1) = O(N)$

也就是説通過遞歸算法解決 階乘問題，不管是其時間複雜度還是空間複雜度均為：$O(N)$，即該算法與數據規模均為 線性關係。由於系統的內存大小是固定的，因此當我們計算的數值所需的函數棧幀空間大於系統的內存大小時，遞歸算法就會出現 棧溢出 的問題；這時我們通過迭代實現，往往是更佳的選擇。

結語

通過今天的學習，我們深入探索了遞歸這一重要的編程思想。讓我們回顧一下本文的核心要點：

遞歸的核心思想是"分而治之"——將複雜的大問題分解為結構相同的子問題，直到問題足夠簡單可以直接解決。
- 這種思想在數學定義遞歸的問題（如階乘、斐波那契數列）、遞歸數據結構（樹、鏈表）以及需要回溯算法的問題中表現出色。
遞歸與迭代各有優劣：
- 遞歸讓代碼更加簡潔清晰，更貼近問題的數學定義，但需要付出性能開銷和棧溢出的風險；
- 迭代雖然代碼相對複雜，但在性能和內存使用上更加安全可控。
實現遞歸的四步法為我們提供了清晰的實踐指南：

$$ 定義函數 \rightarrow 尋找遞歸基 \rightarrow 建立遞進關係 \rightarrow 組合優化 $$

遞歸樹這一工具幫助我們直觀理解遞歸的執行過程，並能夠系統分析算法的時間複雜度和空間複雜度，讓我們對遞歸的性能特徵有了量化認識。

遞歸就像一把雙刃劍——用對了能讓複雜問題迎刃而解，用錯了則可能導致性能災難。關鍵在於根據具體問題特點做出明智選擇：

當問題天然具有遞歸結構時，遞歸往往是最優雅的解決方案；
當性能至關重要或遞歸深度可能很大時，迭代可能是更穩妥的選擇。

希望本文能幫助你不僅理解遞歸的"形"，更能掌握其"神"，在未來的編程實踐中游刃有餘地運用這一強大工具。 互動與分享

點贊👍 - 您的認可是我持續創作的最大動力
收藏⭐ - 方便隨時回顧這些重要的基礎概念
轉發↗️ - 分享給更多可能需要的朋友
評論💬 - 歡迎留下您的寶貴意見或想討論的話題

感謝您的耐心閲讀！關注博主，不錯過更多技術乾貨。我們下一篇再見！

蒙奇D索隆博客

蒙奇D索隆博客

博客 / 詳情