遞歸算法初相識

**

在 C++ 的奇妙世界里，遞歸算法就像是一把神奇的鑰匙，能夠開啟解決復雜問題的大門。那么，究竟什么是遞歸算法呢？簡單來說，遞歸算法就是一種函數調用自身的編程技巧。當一個函數在其定義中直接或間接地調用自己時，我們就稱這個函數使用了遞歸算法。

遞歸算法的核心在于將一個大問題逐步分解為一系列與原問題相似但規模更小的子問題，通過解決這些子問題，最終達到解決原問題的目的。這種 “分而治之” 的思想，使得遞歸算法在處理某些類型的問題時顯得格外簡潔和優雅。

舉個例子，假設我們要計算一個整數 n 的階乘，數學上定義為 n! = n * (n - 1) * (n - 2) * ... * 1。使用遞歸算法，我們可以將這個問題分解為以下兩個部分：

1. 遞歸基：當 n 為 0 或 1 時，n 的階乘為 1，這是遞歸的終止條件，也稱為遞歸基。

1. 遞歸關系：當 n 大于 1 時，n 的階乘等于 n 乘以 (n - 1) 的階乘，即 n! = n * (n - 1)!。這就是遞歸關系，它描述了如何將原問題（計算 n 的階乘）轉化為規模更小的子問題（計算 (n - 1) 的階乘）。

用 C++ 代碼實現計算階乘的遞歸函數如下：

#include <iostream>

// 計算階乘的遞歸函數

int factorial(int n) {

// 遞歸基：n為0或1時，返回1

if (n == 0 || n == 1) {

return 1;

} else {

// 遞歸關系：n的階乘等于n乘以(n - 1)的階乘

return n * factorial(n - 1);

}

}

int main() {

int num = 5;

std::cout << num << "的階乘是：" << factorial(num) << std::endl;

return 0;

}

在上述代碼中，factorial函數通過調用自身來逐步計算階乘。當n為 0 或 1 時，函數直接返回 1，遞歸結束；否則，函數返回n乘以factorial(n - 1)的結果，不斷將問題規模縮小，直到滿足遞歸基條件。

通過這個簡單的例子，我們可以看到遞歸算法的基本結構和工作原理。在后續的內容中，我們將深入探討遞歸算法的更多應用場景和實際案例，一起領略遞歸算法的魅力。

遞歸算法原理剖析

（一）遞歸的 “遞推” 與 “回歸”

遞歸算法的執行過程可以形象地分為兩個階段：“遞推” 與 “回歸”。

在 “遞推” 階段，遞歸函數不斷地調用自身，將原問題逐步分解為規模越來越小的子問題。這個過程就像是在剝洋蔥，每一層遞歸都將問題的規模縮小一點，直到達到遞歸基條件。例如，在計算階乘的例子中，factorial(n)會調用factorial(n - 1)，factorial(n - 1)又會調用factorial(n - 2)，以此類推，直到n為 0 或 1 時，遞推階段結束。

當達到遞歸基條件后，遞歸函數開始進入 “回歸” 階段。在這個階段，遞歸函數從最底層的子問題開始，逐步返回結果，將子問題的解合并起來，最終得到原問題的解。還是以階乘計算為例，當n為 0 或 1 時，factorial函數返回 1，然后factorial(1)將結果返回給factorial(2)，factorial(2)再將結果返回給factorial(3)，以此類推，最終factorial(n)得到n的階乘結果。

通過 “遞推” 與 “回歸” 這兩個階段，遞歸算法巧妙地實現了對復雜問題的求解。這種思想在很多實際問題中都有著廣泛的應用，比如樹形結構的遍歷、數學問題的求解等。

（二）遞歸樹的可視化理解

為了更直觀地理解遞歸算法的執行過程，我們可以使用遞歸樹來進行可視化。遞歸樹是一種樹形結構，其中每個節點表示一次遞歸調用，節點的值表示當前遞歸調用的參數。

以計算階乘factorial(5)為例，其遞歸樹如下所示：

factorial(5)

|

5 * factorial(4)

|

4 * factorial(3)

|

3 * factorial(2)

|

2 * factorial(1)

|

1 * factorial(0)

|

1

在這棵遞歸樹中，根節點是factorial(5)，它的子節點是5 * factorial(4)，表示factorial(5)通過調用factorial(4)來計算結果。以此類推，每一層的節點都表示一次遞歸調用，直到最底層的葉節點factorial(0)，它是遞歸的終止條件，返回值為 1。

通過遞歸樹，我們可以清晰地看到遞歸算法的 “遞推” 與 “回歸” 過程。在遞推階段，遞歸樹從根節點開始向下生長，每一層的節點都表示一次遞歸調用，問題的規模逐漸縮小；在回歸階段，遞歸樹從葉節點開始向上返回結果，將子問題的解逐步合并起來，最終得到原問題的解。

遞歸樹不僅可以幫助我們理解遞歸算法的執行過程，還可以用于分析遞歸算法的時間復雜度和空間復雜度。通過觀察遞歸樹的深度和節點數量，我們可以大致估算出遞歸算法的時間和空間開銷，從而對算法的性能進行評估和優化。

C++ 遞歸算法實戰演練

（一）計算階乘

階乘在數學中是一個常見的概念，對于正整數 n，其階乘 n! 定義為從 1 到 n 的所有正整數的乘積，即 n! = 1×2×3×...×n ，同時規定 0 的階乘為 1，即 0! = 1。

在 C++ 中，我們可以使用遞歸算法來輕松地計算階乘。下面是實現代碼：

#include <iostream>

// 計算階乘的遞歸函數

int factorial(int n) {

// 遞歸基：n為0或1時，返回1

if (n == 0 || n == 1) {

return 1;

} else {

// 遞歸關系：n的階乘等于n乘以(n - 1)的階乘

return n * factorial(n - 1);

}

}

int main() {

int num = 5;

std::cout << num << "的階乘是：" << factorial(num) << std::endl;

return 0;

}

在上述代碼中，factorial函數通過遞歸的方式來計算階乘。當n為 0 或 1 時，函數直接返回 1，這是遞歸的終止條件，也就是遞歸基。當n大于 1 時，函數通過n * factorial(n - 1)來遞歸計算n的階乘，其中factorial(n - 1)會繼續調用自身，直到n達到遞歸基條件。

例如，當計算factorial(5)時，函數的執行流程如下：

1. factorial(5) 調用 factorial(4) ，此時計算 5 * factorial(4) 。

1. factorial(4) 調用 factorial(3) ，此時計算 4 * factorial(3) 。

1. factorial(3) 調用 factorial(2) ，此時計算 3 * factorial(2) 。

1. factorial(2) 調用 factorial(1) ，此時計算 2 * factorial(1) 。

1. factorial(1) 滿足遞歸基條件（n == 1），返回 1。

1. 然后逐步回歸，factorial(2) 返回 2 * 1 = 2 。

1. factorial(3) 返回 3 * 2 = 6 。

1. factorial(4) 返回 4 * 6 = 24 。

1. 最終 factorial(5) 返回 5 * 24 = 120 。

通過這種遞歸的方式，我們可以簡潔地實現階乘的計算。不過，對于較大的n值，遞歸算法可能會導致棧溢出問題，因為每一次遞歸調用都會在棧上分配空間，當遞歸深度過大時，棧空間可能會被耗盡。在實際應用中，對于較大的n，可以考慮使用迭代的方式來計算階乘，以避免棧溢出問題。

（二）斐波那契數列求解

斐波那契數列是一個非常著名的數列，它的規則是：數列的前兩項為 1，從第三項開始，每一項都等于前兩項之和。用數學公式表示為：F (1) = 1，F (2) = 1，F (n) = F (n - 1) + F (n - 2) （n ≥ 3，n ∈ N*） ，數列的前幾項為：1, 1, 2, 3, 5, 8, 13, 21, 34, 55...

在 C++ 中，我們可以使用遞歸算法來求解斐波那契數列。以下是實現代碼：

#include <iostream>

// 遞歸計算斐波那契數列第n項

int fibonacci(int n) {

if (n == 1 || n == 2) {

return 1;

} else {

return fibonacci(n - 1) + fibonacci(n - 2);

}

}

int main() {

int n = 10;

std::cout << "第" << n << "項斐波那契數是：" << fibonacci(n) << std::endl;

return 0;

}

在上述代碼中，fibonacci函數通過遞歸的方式來計算斐波那契數列的第n項。當n為 1 或 2 時，函數直接返回 1，這是遞歸的終止條件。當n大于 2 時，函數通過 fibonacci(n - 1) + fibonacci(n - 2) 來遞歸計算第n項的值，其中fibonacci(n - 1)和fibonacci(n - 2)會繼續調用自身，直到滿足遞歸基條件。

然而，使用遞歸方法求解斐波那契數列存在性能問題。從遞歸樹的角度來看，隨著n的增大，遞歸樹會變得非常龐大，因為會有大量的重復計算。例如，在計算fibonacci(5)時，fibonacci(3)會被計算兩次，fibonacci(2)會被計算三次。當n較大時，這種重復計算會導致計算量呈指數級增長，時間復雜度為 O (2^n) ，空間復雜度為 O (n) ，因為遞歸調用會占用棧空間，遞歸深度最大為n。

為了提高性能，可以使用迭代的方式來求解斐波那契數列。迭代方法通過循環逐步計算每一項的值，避免了重復計算，時間復雜度可以降低到 O (n) ，空間復雜度可以優化到 O (1) 。以下是迭代實現的代碼：

#include <iostream>

// 迭代計算斐波那契數列第n項

int fibonacciIterative(int n) {

if (n == 1 || n == 2) {

return 1;

}

int a = 1, b = 1, result;

for (int i = 3; i <= n; i++) {

result = a + b;

a = b;

b = result;

}

return result;

}

int main() {

int n = 10;

std::cout << "第" << n << "項斐波那契數（迭代法）是：" << fibonacciIterative(n) << std::endl;

return 0;

}

在實際應用中，根據具體需求選擇合適的方法來求解斐波那契數列。如果n較小，遞歸方法簡單直觀；如果n較大，為了提高效率，建議使用迭代方法。

（三）漢諾塔問題解決

漢諾塔問題是一個經典的遞歸問題，它源于一個古老的傳說。傳說中，有三根柱子 A、B、C，在 A 柱上有若干個大小不同的圓盤，按照從小到大的順序疊放，最大的圓盤在最下面。現在要將 A 柱上的所有圓盤移動到 C 柱上，每次只能移動一個圓盤，并且在移動過程中，大圓盤不能放在小圓盤上面，可以借助 B 柱作為輔助。

解決漢諾塔問題的遞歸思路如下：

1. 如果只有一個圓盤，直接將它從源柱（假設為 A 柱）移動到目標柱（假設為 C 柱）。

1. 如果有n個圓盤，先將前n - 1個圓盤從源柱（A 柱）通過目標柱（C 柱）移動到輔助柱（B 柱）。

1. 然后將第n個圓盤從源柱（A 柱）直接移動到目標柱（C 柱）。

1. 最后再將前n - 1個圓盤從輔助柱（B 柱）通過源柱（A 柱）移動到目標柱（C 柱）。

以下是使用 C++ 實現漢諾塔問題的遞歸代碼：

#include <iostream>

// 遞歸函數，用于解決漢諾塔問題

void hanoi(int n, char from, char to, char aux) {

if (n == 1) {

// 如果只有一個盤子，直接從源柱移動到目標柱

std::cout << "Move disk 1 from " << from << " to " << to << std::endl;

return;

}

// 將前n - 1個盤子從源柱移動到輔助柱

hanoi(n - 1, from, aux, to);

// 將第n個盤子從源柱移動到目標柱

std::cout << "Move disk " << n << " from " << from << " to " << to << std::endl;

// 將前n - 1個盤子從輔助柱移動到目標柱

hanoi(n - 1, aux, to, from);

}

int main() {

int n = 3; // 盤子數量

hanoi(n, 'A', 'C', 'B');

return 0;

}

在上述代碼中，hanoi函數接受四個參數：盤子的數量n，源柱from，目標柱to，輔助柱aux。當n為 1 時，直接輸出從from到to的移動操作。否則，先遞歸調用hanoi函數將前n - 1個盤子從from移動到aux，然后輸出將第n個盤子從from移動到to的操作，最后再遞歸調用hanoi函數將前n - 1個盤子從aux移動到to。

以 3 個盤子為例，遞歸過程如下：

1. 初始狀態：A 柱上有 3 個盤子，B 柱和 C 柱為空。

1. 第一次遞歸調用hanoi(2, 'A', 'B', 'C') ，將前 2 個盤子從 A 柱通過 C 柱移動到 B 柱。

• • 第二次遞歸調用hanoi(1, 'A', 'C', 'B') ，將第 1 個盤子從 A 柱移動到 C 柱。

• • 輸出 “Move disk 1 from A to C” 。

• • 第二次遞歸調用hanoi(1, 'B', 'C', 'A') ，將第 2 個盤子從 B 柱移動到 C 柱。

• • 輸出 “Move disk 2 from B to C” 。

1. 輸出 “Move disk 3 from A to B” ，將第 3 個盤子從 A 柱移動到 B 柱。

1. 第二次遞歸調用hanoi(2, 'C', 'B', 'A') ，將前 2 個盤子從 C 柱通過 A 柱移動到 B 柱。

• • 第二次遞歸調用hanoi(1, 'C', 'A', 'B') ，將第 1 個盤子從 C 柱移動到 A 柱。

• • 輸出 “Move disk 1 from C to A” 。

• • 第二次遞歸調用hanoi(1, 'A', 'B', 'C') ，將第 2 個盤子從 A 柱移動到 B 柱。

• • 輸出 “Move disk 2 from A to B” 。

通過遞歸算法，我們可以巧妙地解決漢諾塔問題，清晰地展示了遞歸在解決復雜問題時的強大能力和簡潔性。

遞歸算法的優缺點

（一）優點

1. 代碼簡潔優雅：遞歸算法能夠用簡潔的代碼表達復雜的邏輯。以計算階乘為例，遞歸實現的代碼非常緊湊，只需寥寥數行，就能夠清晰地表達出階乘的計算邏輯，相比迭代實現，代碼的行數明顯減少，邏輯也更加直觀。這種簡潔性使得代碼的可讀性大大提高，其他人在閱讀和理解代碼時更加容易，能夠快速把握算法的核心思想。

1. 符合思維習慣：遞歸的思想與人類解決某些問題的思維方式非常相似。當我們面對一個復雜問題時，常常會不自覺地將其分解為多個小問題，然后逐步解決這些小問題，最終得到原問題的解。遞歸算法正是這種思維方式的直接體現，它通過函數自身的調用，將大問題不斷分解為小問題，使得算法的設計和實現更加自然流暢。例如，在解決漢諾塔問題時，遞歸算法能夠清晰地模擬我們在腦海中思考如何移動圓盤的過程，讓我們更容易理解和實現解決方案。

1. 適用于分治問題：對于那些可以分解為相互獨立、規模較小且結構相似的子問題的情況，遞歸算法是非常合適的選擇。分治算法的核心就是將原問題分解為多個子問題，分別求解子問題，然后將子問題的解合并得到原問題的解。遞歸算法天然地支持這種分治思想，能夠方便地實現分治算法。例如，歸并排序和快速排序等經典的排序算法，都是基于分治思想，使用遞歸算法實現的。在歸并排序中，通過遞歸地將數組分成兩半，分別對兩半進行排序，然后將排序好的兩半合并起來，最終實現整個數組的排序。

（二）缺點

1. 棧空間消耗大：每一次遞歸調用都會在系統棧中分配新的棧幀，用于存儲函數的參數、局部變量和返回地址等信息。當遞歸深度過大時，棧空間會被大量占用，如果超過了系統棧的容量限制，就會導致棧溢出錯誤。例如，在計算較大數的階乘或者深度較深的樹形結構遍歷中，如果使用遞歸算法，很容易因為棧溢出而導致程序崩潰。

1. 容易棧溢出：由于遞歸調用是通過棧來實現的，而棧的大小是有限的。如果遞歸函數沒有正確設置終止條件，或者在某些情況下遞歸深度過大，就會導致棧溢出。棧溢出是一種嚴重的錯誤，它會使程序異常終止，并且很難調試和排查問題。比如，在一個沒有終止條件的遞歸函數中，函數會不斷地調用自身，棧幀會不斷地壓入棧中，最終導致棧溢出。

1. 效率較低：遞歸算法中往往存在大量的重復計算。例如，在計算斐波那契數列時，簡單的遞歸實現會多次計算相同的子問題，隨著數列項數的增加，計算量會呈指數級增長，導致算法效率極低。這是因為遞歸算法在每次調用時，都沒有保存之前計算過的結果，而是重新計算，浪費了大量的時間和計算資源。相比之下，使用迭代算法或者記憶化遞歸（保存中間結果）可以有效地避免重復計算，提高算法的效率。

遞歸算法優化策略

（一）記憶化

記憶化（Memoization）是一種優化遞歸算法的有效策略，其核心原理是將已經計算過的結果存儲起來，當再次遇到相同的子問題時，直接從存儲中獲取結果，而無需重新計算，從而避免了大量的重復計算，顯著提高算法效率。

以斐波那契數列的計算為例，在之前的實現中，簡單遞歸方法存在嚴重的重復計算問題。隨著數列項數n的增大，計算量呈指數級增長，時間復雜度為 O (2^n) 。使用記憶化技術后，我們可以用一個數組或哈希表來記錄已經計算過的斐波那契數。

以下是使用 C++ 實現記憶化遞歸計算斐波那契數列的代碼：

#include <iostream>

#include <vector>

// 記憶化數組，初始化為-1，表示尚未計算

std::vector<int> memo;

int fibonacci(int n) {

// 檢查是否已經計算過

if (memo[n] != -1) {

return memo[n];

}

if (n == 0 || n == 1) {

// 記錄基本情況的結果

memo[n] = n;

} else {

// 遞歸計算并記錄結果

memo[n] = fibonacci(n - 1) + fibonacci(n - 2);

}

return memo[n];

}

int main() {

int n = 10;

// 初始化記憶化數組

memo.resize(n + 1, -1);

std::cout << "第" << n << "項斐波那契數是：" << fibonacci(n) << std::endl;

return 0;

}

在這段代碼中，memo數組用于存儲已經計算過的斐波那契數。在fibonacci函數中，每次計算前先檢查memo[n]是否已經有值，如果有則直接返回，避免了重復計算。通過這種方式，時間復雜度降低到了 O (n) ，因為每個子問題最多只需要計算一次。

（二）尾遞歸優化

尾遞歸是遞歸的一種特殊形式，其特點是在遞歸調用返回時，除了返回遞歸調用的結果外，不再進行任何其他操作。也就是說，遞歸調用是函數執行的最后一個操作。尾遞歸的優勢在于它可以避免棧溢出問題，因為在尾遞歸中，編譯器可以優化遞歸調用，使得每次遞歸調用時不需要保存當前函數的棧幀，而是直接重用當前棧幀，從而大大減少了棧空間的占用。

以計算階乘為例，普通的遞歸實現如下：

int factorial(int n) {

if (n == 0 || n == 1) {

return 1;

} else {

return n * factorial(n - 1);

}

}

在這個實現中，每次遞歸調用返回后，還需要進行乘法運算，這不是尾遞歸。

下面是尾遞歸優化后的階乘實現：

int factorial_helper(int n, int acc = 1) {

if (n == 0 || n == 1) {

return acc;

} else {

// 尾遞歸調用，直接返回遞歸結果

return factorial_helper(n - 1, n * acc);

}

}

int factorial(int n) {

return factorial_helper(n);

}

在factorial_helper函數中，acc是一個累加器，用于保存中間結果。每次遞歸調用時，將n和acc相乘，并將結果傳遞給下一層遞歸。當n達到終止條件時，直接返回acc，這是典型的尾遞歸形式。

在支持尾遞歸優化的編譯器中，這種尾遞歸實現會被優化成循環結構，從而避免棧溢出問題，提高程序的性能和穩定性。例如，GCC 和 Clang 等編譯器在開啟優化選項（如-O2或-O3）時，會對尾遞歸進行優化。不過，并非所有編譯器都能有效地進行尾遞歸優化，在實際應用中，需要根據具體的編譯器和場景來選擇合適的優化策略。

遞歸算法應用場景拓展

遞歸算法作為一種強大的編程技術，在眾多領域都有著廣泛的應用。除了前面介紹的階乘計算、斐波那契數列求解和漢諾塔問題解決之外，遞歸在數學計算、數據結構遍歷、經典算法設計等方面也發揮著重要作用。

（一）數學計算領域

在數學計算中，遞歸算法常用于解決各種具有遞歸性質的數學問題。例如，計算阿克曼函數（Ackermann function）。阿克曼函數是一個典型的遞歸函數，它的定義如下：\( A(m, n) = \begin{cases} n + 1 & \text{if } m = 0 \\ A(m - 1, 1) & \text{if } m \gt 0 \text{ and } n = 0 \\ A(m - 1, A(m, n - 1)) & \text{if } m \gt 0 \text{ and } n \gt 0 \end{cases} \)

用 C++ 實現阿克曼函數的遞歸代碼如下：

#include <iostream>

// 計算阿克曼函數的遞歸函數

int ackermann(int m, int n) {

if (m == 0) {

return n + 1;

} else if (n == 0) {

return ackermann(m - 1, 1);

} else {

return ackermann(m - 1, ackermann(m, n - 1));

}

}

int main() {

int m = 3, n = 4;

std::cout << "A(" << m << ", " << n << ") = " << ackermann(m, n) << std::endl;

return 0;

}

阿克曼函數的計算過程非常復雜，遞歸深度會隨著m和n的增大而迅速增加，這也體現了遞歸在處理復雜數學問題時的能力。

（二）數據結構遍歷

遞歸在樹形結構和圖形結構的遍歷中有著廣泛的應用。以二叉樹為例，二叉樹的前序遍歷、中序遍歷和后序遍歷都可以用遞歸算法輕松實現。

以下是用 C++ 實現二叉樹中序遍歷的遞歸代碼：

#include <iostream>

// 定義二叉樹節點結構

struct TreeNode {

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

// 中序遍歷遞歸函數

void inorderTraversal(TreeNode* root) {

if (root != nullptr) {

inorderTraversal(root->left);

std::cout << root->val << " ";

inorderTraversal(root->right);

}

}

int main() {

// 構建簡單二叉樹

TreeNode* root = new TreeNode(1);

root->right = new TreeNode(2);

root->right->left = new TreeNode(3);

std::cout << "中序遍歷結果: ";

inorderTraversal(root);

return 0;

}

在這段代碼中，inorderTraversal函數通過遞歸地遍歷左子樹、輸出當前節點值、遞歸地遍歷右子樹，實現了二叉樹的中序遍歷。這種遞歸實現方式簡潔明了，充分體現了遞歸在處理樹形結構時的優勢。

在圖的遍歷中，深度優先搜索（DFS）算法也常常使用遞歸實現。假設圖以鄰接表表示，以下是使用遞歸實現深度優先搜索的代碼示例：

#include <iostream>

#include <vector>

// 圖的鄰接表表示

class Graph {

int V; // 頂點數

std::vector<std::vector<int>> adj; // 鄰接表

public:

Graph(int v) : V(v), adj(v) {}

void addEdge(int v, int w) {

adj[v].push_back(w);

}

void DFSUtil(int v, std::vector<bool>& visited) {

visited[v] = true;

std::cout << v << " ";

for (int i = 0; i < adj[v].size(); ++i) {

if (!visited[adj[v][i]]) {

DFSUtil(adj[v][i], visited);

}

}

}

void DFS(int v) {

std::vector<bool> visited(V, false);

DFSUtil(v, visited);

}

};

int main() {

Graph g(4);

g.addEdge(0, 1);

g.addEdge(0, 2);

g.addEdge(1, 2);

g.addEdge(2, 0);

g.addEdge(2, 3);

g.addEdge(3, 3);

std::cout << "從頂點 2 開始的深度優先搜索: ";

g.DFS(2);

return 0;

}

在這個示例中，DFSUtil函數通過遞歸地訪問當前頂點的未訪問鄰接頂點，實現了圖的深度優先搜索。遞歸使得深度優先搜索的實現更加直觀和簡潔。

（三）經典算法設計

遞歸在許多經典算法設計中扮演著關鍵角色。例如，歸并排序（Merge Sort）算法是一種基于分治思想的排序算法，它的實現就離不開遞歸。歸并排序的基本思想是將一個數組分成兩個子數組，對每個子數組進行排序，然后將排序好的子數組合并起來。

以下是用 C++ 實現歸并排序的遞歸代碼：

#include <iostream>

#include <vector>

// 合并兩個有序子數組

void merge(std::vector<int>& arr, int left, int mid, int right) {

int n1 = mid - left + 1;

int n2 = right - mid;

std::vector<int> L(n1), R(n2);

for (int i = 0; i < n1; ++i) {

L[i] = arr[left + i];

}

for (int j = 0; j < n2; ++j) {

R[j] = arr[mid + 1 + j];

}

int i = 0, j = 0, k = left;

while (i < n1 && j < n2) {

if (L[i] <= R[j]) {

arr[k] = L[i];

++i;

} else {

arr[k] = R[j];

++j;

}

++k;

}

while (i < n1) {

arr[k] = L[i];

++i;

++k;

}

while (j < n2) {

arr[k] = R[j];

++j;

++k;

}

}

// 歸并排序遞歸函數

void mergeSort(std::vector<int>& arr, int left, int right) {

if (left < right) {

int mid = left + (right - left) / 2;

mergeSort(arr, left, mid);

mergeSort(arr, mid + 1, right);

merge(arr, left, mid, right);

}

}

int main() {

std::vector<int> arr = {12, 11, 13, 5, 6, 7};

int n = arr.size();

std::cout << "原始數組: ";

for (int num : arr) {

std::cout << num << " ";

}

std::cout << std::endl;

mergeSort(arr, 0, n - 1);

std::cout << "排序后的數組: ";

for (int num : arr) {

std::cout << num << " ";

}

std::cout << std::endl;

return 0;

}

在這段代碼中，mergeSort函數通過遞歸地將數組分成兩半，分別對兩半進行排序，然后使用merge函數將排序好的兩半合并起來，最終實現整個數組的排序。遞歸的使用使得歸并排序的實現邏輯清晰，易于理解和維護。

通過以上幾個方面的應用場景拓展，我們可以看到遞歸算法在解決各種復雜問題時的強大能力和廣泛適用性。在實際編程中，根據問題的特點和需求，合理地運用遞歸算法，可以使代碼更加簡潔、高效，同時也能更好地體現算法的思想和邏輯。

總結與展望

遞歸算法作為 C++ 編程中的一項重要技術，以其獨特的 “分而治之” 思想，為解決復雜問題提供了簡潔而優雅的方案。從基本的階乘計算到復雜的漢諾塔問題，從數學計算領域到數據結構遍歷和經典算法設計，遞歸算法都展現出了強大的適應性和解決問題的能力。

通過對遞歸算法原理的深入剖析，我們了解了遞歸的 “遞推” 與 “回歸” 過程，以及遞歸樹在可視化理解遞歸執行過程中的作用。在實戰演練部分，我們通過計算階乘、求解斐波那契數列和解決漢諾塔問題，親身體驗了遞歸算法的實現方式和應用場景。同時，我們也認識到遞歸算法雖然具有代碼簡潔、符合思維習慣等優點，但也存在棧空間消耗大、容易棧溢出和效率較低等缺點。為了克服這些缺點，我們探討了記憶化和尾遞歸優化等策略，這些策略能夠有效地提高遞歸算法的性能和穩定性。

在應用場景拓展方面，遞歸算法在數學計算領域的阿克曼函數計算、數據結構遍歷中的二叉樹遍歷和圖的深度優先搜索、經典算法設計中的歸并排序等方面都有著廣泛的應用。這些應用充分展示了遞歸算法在不同領域的重要性和實用性。

遞歸算法是 C++ 編程中不可或缺的一部分，它不僅是解決問題的有力工具，也是培養編程思維和邏輯能力的重要途徑。希望讀者通過本文的介紹，能夠對遞歸算法有更深入的理解和掌握，在今后的編程實踐中靈活運用遞歸算法，解決更多復雜的問題。同時，也期待讀者能夠進一步探索遞歸算法的更多應用場景和優化策略，不斷提升自己的編程水平和解決問題的能力。