C++ 遞迴（遞迴函式）

---

---

遞迴是一種程式設計技術，其中一個函式一遍又一遍地呼叫自身，並使用修改後的引數，直到它到達其基本情況，遞迴停止。

它將問題分解成更小、更容易管理的子問題，遞迴允許對複雜問題進行優雅和更好的解決方案。

遞迴函式

遞迴函式是一種特別用於遞迴的函式，其中一個函式直接或間接地呼叫自身以解決問題。它必須至少包含一個基本情況來終止遞迴和一個遞迴情況，其中函式呼叫自身。

• 基本情況 - 它是遞迴在達到特定條件後停止或結束的情況。
• 遞迴情況 - 它是函式一遍又一遍地呼叫自身並遞減值的情況，直到它到達其基本情況。

建立遞迴函式

以下語法用於在 C++ 中實現遞迴函式：

function name(param_1, param_2..){
   <base condition>

   <function body>

   <return statement>
}

這裡，

• 其中，function name(param_1, param_2..) 是一個宣告為“name”的函式，根據需要傳遞多個引數。
• 現在函式體被分為三個子類別：基本條件、函式體和返回語句。
• 在基本條件中，我們將定義其基本情況，遞迴必須在其中停止或結束。
• 在函式體中，將定義一個遞迴情況，我們需要根據需要一遍又一遍地呼叫該函式。
• 最後，return 語句將返回函式的最終輸出。

呼叫遞迴函式

呼叫遞迴函式就像呼叫任何其他函式一樣，您將在 int main() 函式體中使用函式名並提供必要的引數。

要呼叫遞迴函式，請使用以下語法：

func_name(value);

遞迴示例

下面是 C++ 中遞迴函式的示例。在這裡，我們使用遞迴計算數字的階乘：

#include <iostream>
using namespace std;

// Recursive Function to Calculate Factorial
int factorial(int num) {
   // Base case
   if (num <= 1) {
      return 1;
   }
   // Recursive case
   else {
      return num * factorial(num - 1);
   }
}

int main() {
   int positive_number;
   cout << "Enter a positive integer: ";
   cin >> positive_number;
   if (positive_number < 0) {
      cout << "Wrong Input, Factorial is not Defined for Negative Integer" << endl;
   } else {
      cout << "Factorial of " << positive_number << " is " << factorial(positive_number) << endl;
   }
   return 0;
}

輸出

Enter a positive integer: 4 (input)
Factorial of 4 is 24

解釋

如果將輸入 int positive_number 作為 4，它將整數傳送到函式名“factorial”作為 factorial(4)

初始呼叫：factorial(4)

此函式將檢查基本情況 (n<=1)，因為它不滿足基本情況，因此繼續執行遞迴情況並計算為“4 * factorial(3)”。

第二次呼叫：factorial(3)

此函式將再次檢查基本情況，因為它不滿足它，因此將再次繼續執行遞迴情況，並計算為“3 * factorial(2)”。

第三次呼叫：factorial(2)

檢查基本情況並計算“2 * factorial(1)”

第四次呼叫：factorial(1)

檢查基本情況，現在由於函式滿足小於或等於 1 的此基本情況條件，因此它將返回 1。

展開棧

現在，遞迴呼叫將開始返回：在第四次呼叫之後，它將再次從後面開始，首先返回到第三次呼叫。

返回到第三次呼叫：factorial(2)

我們已經有了 factorial(1) = 1，因此 factorial(2) 將返回“2 * factorial(1)”，即“2 * 1”，它返回為 factorial(2) 等於 2。

返回到第二次呼叫：factorial(3)

現在，factorial(2) 為 2，因此 factorial(3) 等於“3 * 2”，即 6。

返回到初始呼叫：factorial(4)

我們有 factoria(3) 返回 6，因此，factorial(4) 返回“4 * 6 = 24”。

遞迴型別

遞迴可以分為兩種主要型別，每種型別都有自己的子類別：

1. 直接遞迴

當函式直接呼叫自身時發生直接遞迴：

簡單直接遞迴

該函式使用問題的更簡單或更小的例項呼叫自身。它用於解決諸如階乘計算、斐波那契數列生成等問題。

尾遞迴

直接遞迴的一種形式，其中遞迴呼叫是函式中的最後一個操作。它用於解決累積計算和列表處理問題。

int factorial(int n, int result = 1) {
   if (n <= 1) {
      return result;
   } else {
      return factorial(n - 1, n * result);  // Tail recursive call
   }
}

頭遞迴

在任何其他操作之前進行遞迴呼叫。處理在遞迴呼叫返回後發生。它用於樹遍歷和輸出生成。

void printNumbers(int n) {
   if (n > 0) {
      printNumbers(n - 1);  // Recursive call first
      cout << n << " ";     // Processing after recursive call
   }
}

線性遞迴

每個函式呼叫都生成正好一個遞迴呼叫，形成一個線性的呼叫鏈。它用於簡單的計數或求和。

int linearRecursion(int n) {
   if (n <= 0) {
      return 0;
   } else {
      return linearRecursion(n - 1) + 1;  // Linear recursive call
   }
}

2. 間接遞迴

當一個函式呼叫另一個函式時發生間接遞迴，這最終會導致原始函式被呼叫。這涉及兩個或多個函式相互呼叫。

相互遞迴

在相互遞迴中，兩個或多個函式以遞迴方式相互呼叫，形成迴圈依賴關係。它用於偶數和奇數分類以及語法分析。

#include <iostream>
using namespace std;

void even(int n);
void odd(int n);

void even(int n) {
   if (n == 0) {
      cout << "Even" << endl;
   } else {
      odd(n - 1);  // Calls odd
   }
}

void odd(int n) {
   if (n == 0) {
      cout << "Odd" << endl;
   } else {
      even(n - 1);  // Calls even
   }
}

int main() {
   even(4);  
   // Outputs: Even
   odd(5);   
   // Outputs: Odd
   return 0;
}

輸出

Even
Even

巢狀遞迴

巢狀遞迴是一種間接遞迴的形式，其中一個遞迴函式在其自己的遞迴呼叫中進行另一個遞迴呼叫。它用於解決複雜的數學和演算法問題。

#include <iostream>
using namespace std;

int nestedRecursion(int n) {
   if (n > 100) {
      return n - 10;
   } else {
      return nestedRecursion(nestedRecursion(n + 11));  // Nested recursive calls
   }
}

int main() {
   cout << nestedRecursion(95) << endl; // Outputs: 105
   return 0;
}

輸出

91

遞迴的優點

• 簡單性和減少樣板程式碼 - 遞迴有助於簡化解決具有內建遞迴結構的問題，例如處理樹或透過使其更易於理解和實現來解決組合問題。
• 回溯 - 遞迴非常適合回溯演算法，這些演算法涉及檢查所有可能的解決方案以找到滿足某些條件的解決方案。
• 分治問題的有效解決方案 - 遞迴非常適合分治演算法，其中問題被分解成更小的子部分並逐一解決。這使得解決問題更有效率和更容易。

遞迴與迭代

遞迴是一種函式一遍又一遍地呼叫自身並使用修改後的引數直到到達停止遞迴的基本情況的方法。而迭代涉及使用迴圈（例如 for、while 或 do-while），其中它涉及重複執行程式碼塊，直到滿足某個條件。

遞迴或迭代：何時使用？

遞迴

• 可以細分為類似子問題或具有自然遞迴模式（如樹遍歷或組合任務）且深度可控的問題。
• 當用戶需要簡單、更乾淨和可讀的程式碼時，因為它提供了乾淨、正確排列的程式碼。
• 示例：樹和圖遍歷、分治演算法（如快速排序和歸併排序），以及涉及回溯的問題（如解決迷宮或謎題）。

迭代

• 從記憶體和執行時間方面來看，迭代解決方案通常更有效，並且涉及簡單的重複。
• 對於需要簡單迴圈的問題，因為迭代通常更直接且更高效。
• 對於需要大量重複的問題，迭代更穩定，因為它不會冒堆疊溢位的風險。
• 示例：陣列、向量和列表的迴圈，需要簡單的數學計算和程式碼塊的重複執行。

遞迴和迭代的比較

遞迴的侷限性

以下是遞迴的侷限性：

• 記憶體消耗 - 每次遞迴呼叫都會在呼叫棧中新增一個新的幀，這可能會消耗大量的記憶體。
• 堆疊溢位風險 - 由於遞迴依賴於呼叫棧來管理函式呼叫，因此深度遞迴會導致堆疊溢位，因為它超過了堆疊大小限制。
• 效能開銷 - 遞迴函式可能不如迭代函式高效，因為它們涉及多個函式呼叫的開銷和管理呼叫棧，這會嚴重影響效能，尤其是在深度遞迴的情況下。
• 除錯複雜性 - 除錯遞迴程式碼可能具有挑戰性，尤其是在處理複雜遞迴或大型遞迴深度時。它需要仔細處理基本情況和邏輯。
• 空間複雜度 - 由於遞迴中的呼叫棧，它會導致消耗大量記憶體。