前導
遞迴就是函式在執行過程中呼叫自身，並通過結束條件和呼叫堆疊來解決問題。
這種方式通常用於解決可以分解為相同問題的子問題的情況。
在下面圖片中，如果將呼叫函式 B 改為呼叫函式 A 本身，那麼這就是一個典型的遞迴結構。
具體來說:
- 函式 A 在執行過程中呼叫了自身（即 A）。
- 每次呼叫都會產生一個新的執行環境（包括參數、區域變數、返回值址等）。
- 這些執行環境會按照呼叫順序被壓入呼叫堆疊（Call Stack），直到遞迴結束條件被滿足。
遞迴的關鍵要素
- 遞迴結束條件（Base Case）：
- 這是遞迴的終止條件，確保遞迴不會無限進行下去。
- 例如，在計算階乘時，
factorial(0) = 1就是一個結束條件。
- 遞迴呼叫（Recursive Call）：
- 函式在執行過程中呼叫自身，並將問題分解為更小的子問題。
- 例如，
factorial(n) = n * factorial(n-1)。
- 呼叫堆疊（Call Stack）：
- 每次遞迴呼叫都會產生一個新的執行環境，這些環境會被壓入堆疊。
- 當遞迴結束條件滿足時，堆疊會開始彈出(最後放進堆疊的最先被取出)，也就是依次返回結果。
現在我們先來實作圖片中的程式碼:
程式碼實作
#include <stdio.h>
// 函式 B
void B() {
printf("進入函式 B\n");
printf("離開函式 B\n");
}
// 函式 A
void A() {
printf("進入函式 A\n");
B(); // 在 A 中呼叫 B
printf("離開函式 A\n");
}
// 主函式
int main() {
printf("Start\n");
A(); // 在 main 中呼叫 A
printf("End\n");
return 0;
}
輸出:
Start
進入函式 A
進入函式 B
離開函式 B
離開函式 A
End
而遞迴就只是呼叫本身並添加結束條件而已:
#include <stdio.h>
// 函式 A（遞迴函式）
void A(int n) {
printf("進入函式 A，n = %d\n", n);
if (n > 0) {
A(n - 1); // 遞迴呼叫 A
}
printf("離開函式 A，n = %d\n", n);
}
// 主函式
int main() {
printf("進入函式 main\n");
A(2); // 在 main 中呼叫 A，並傳入參數 n = 2
printf("離開函式 main\n");
return 0;
}
輸出:
Start
進入函式 A，n = 2
進入函式 A，n = 1
進入函式 A，n = 0
離開函式 A，n = 0
離開函式 A，n = 1
離開函式 A，n = 2
End
進階遞迴使用示例
接著，我們以遞迴實現迴文檢查的邏輯，幫助你更加理解。
#include <stdio.h>
#include <string.h>
// 遞迴函式：檢查字串是否為迴文
int isPalindrome(char str[], int left, int right) {
// 當 left >= right 時，表示檢查完成，是迴文(結束條件或稱基本情況)
if (left >= right) {
return 1; // 是迴文
}
// 如果左右字符不相等，則不是迴文(結束條件或稱基本情況)
if (str[left] != str[right]) {
return 0; // 不是迴文
}
// 遞迴檢查下一對字符
return isPalindrome(str, left + 1, right - 1);
}
// 主函式
int main() {
char str[] = "madam"; // 要檢查的字串
int length = strlen(str);
// 呼叫遞迴函式檢查是否為迴文
if (isPalindrome(str, 0, length - 1)) {
printf("'%s' 是迴文\n", str);
} else {
printf("'%s' 不是迴文\n", str);
}
return 0;
}
步驟解析
例子 1："abcda"
字串內容:
索引: 0 1 2 3 4
字符: a b c d a
執行過程:
- 初始呼叫：
isPalindrome("abcda", 0, 4)- 比較
str[0]('a') 和str[4]('a')，相等。 - return
isPalindrome("abcda", 1, 3)。意思就是返回一個遞迴函式。所以返回的結果有待遞迴函式執行。
- 第一次遞迴：
isPalindrome("abcda", 1, 3)- 比較
str[1]('b') 和str[3]('b')，不相等。 - 返回 0（不是迴文）。
- 返回結果：
- 因為
isPalindrome("abcda", 1, 3)的返回結果為0，isPalindrome("abcda", 0, 4)中的return isPalindrome("abcda", 1, 3)即為 return 0; - 最終結果為 （不是迴文）。
- 因為
輸出:
'abcda' 不是迴文例子 2："madam"
字串內容:
索引: 0 1 2 3 4
字符: m a d a m
執行過程:
- 初始呼叫：
isPalindrome("madam", 0, 4)- 比較
str[0]('m') 和str[4]('m')，相等。 return isPalindrome("madam", 1, 3)。意思就是返回一個遞迴函式。所以返回的結果有待遞迴函式執行。
- 第一次遞迴：
isPalindrome("madam", 1, 3)- 比較
str[1]('a') 和str[3]('a')，相等。 return isPalindrome("madam", 2, 2)。意思就是返回一個遞迴函式。所以返回的結果有待遞迴函式執行。
- 第二次遞迴：
isPalindrome("madam", 2, 2)- 因為 left == right，情況達成，返回 1（是迴文）。
- 返回結果：
- 所有遞迴呼叫都返回 1，最終結果為 1（是迴文）。
輸出:
'madam' 是迴文河內塔遞迴問題
最後，河內塔是一個經典的遞迴問題，問題描述:
- 有三根柱子，分別稱為 A、B、C。
- 在柱子 A 上有 n 個大小不同的圓盤，圓盤從上到下依序變大。
- 目標是將所有圓盤從柱子 A 移動到柱子 C。
移動需要遵守以下規則：
- 一次只能移動一個圓盤。
- 不能將較大的圓盤放在較小的圓盤上。
- 可以使用一根輔助柱子。
遞迴解法
我們可以用遞迴的方式來解決這個問題。以下是遞迴的思路：
- 基本情況：如果只有一個圓盤（n = 1），直接將它從柱子 A 移動到柱子 C。也就是直接將圓盤從
source移動到target。 - 遞迴情況：
- 將
n-1個圓盤從柱子A移動到柱子B（使用柱子C作為輔助）。 - 將第
n個圓盤（最大的圓盤）從柱子A移動到柱子C。 - 將
n-1個圓盤從柱子B移動到柱子C（使用柱子A作為輔助）。
- 將
程式碼
#include <stdio.h>
// 河內塔遞迴函式
void hanoi(int n, char source, char auxiliary, char target) {
if (n == 1) {
// 基本情況：只有一個圓盤，直接移動
printf("將圓盤 1 從 %c 移動到 %c\n", source, target);
} else {
// 遞迴步驟：
// 1. 將 n-1 個圓盤從 source 移動到 auxiliary（使用 target 作為輔助）
hanoi(n - 1, source, target, auxiliary);
// 2. 將第 n 個圓盤從 source 移動到 target
printf("將圓盤 %d 從 %c 移動到 %c\n", n, source, target);
// 3. 將 n-1 個圓盤從 auxiliary 移動到 target（使用 source 作為輔助）
hanoi(n - 1, auxiliary, source, target);
}
}
// 主函式
int main() {
int n = 3; // 圓盤數量
printf("河內塔解決方案（n = %d）：\n", n);
hanoi(n, 'A', 'B', 'C'); // 將圓盤從 A 移動到 C，使用 B 作為輔助
return 0;
}
程式碼解析
hanoi函式：- 這是遞迴函式，用於解決河內塔問題。
- 參數：
n：當前要移動的圓盤數量。source：起始柱子。target：目標柱子。auxiliary：輔助柱子。
- 基本情況： 當
n == 1時，直接將圓盤從source移動到target。 - 遞迴情況：
- 將
n-1個圓盤從source移動到auxiliary（使用target作為輔助）。 - 將第
n個圓盤從source移動到target。 - 將
n-1個圓盤從auxiliary移動到target（使用source作為輔助）。
- 將
main函式：- 定義圓盤數量
n。 - 呼叫
hanoi函式，開始解決問題。
- 定義圓盤數量
輸出:
河內塔解決方案（n = 3）：
將圓盤 1 從 A 移動到 C
將圓盤 2 從 A 移動到 B
將圓盤 1 從 C 移動到 B
將圓盤 3 從 A 移動到 C
將圓盤 1 從 B 移動到 A
將圓盤 2 從 B 移動到 C
將圓盤 1 從 A 移動到 C
補充示意圖
- n=2 的遞迴呼叫樹:
hanoi(2, A, B, C)
├── hanoi(1, A, C, B) → 將圓盤 1 從 A 移動到 B
├── 將圓盤 2 從 A 移動到 C
└── hanoi(1, B, A, C) → 將圓盤 1 從 B 移動到 C
- n=3 的遞迴呼叫樹:
hanoi(3, A, B, C)
├── hanoi(2, A, C, B)
│ ├── hanoi(1, A, B, C) → 將圓盤 1 從 A 移動到 C
│ ├── 將圓盤 2 從 A 移動到 B
│ └── hanoi(1, C, A, B) → 將圓盤 1 從 C 移動到 B
├── 將圓盤 3 從 A 移動到 C
└── hanoi(2, B, A, C)
├── hanoi(1, B, C, A) → 將圓盤 1 從 B 移動到 A
├── 將圓盤 2 從 B 移動到 C
└── hanoi(1, A, B, C) → 將圓盤 1 從 A 移動到 C
- 這個樹狀結構反映了河內塔的主要遞迴邏輯：
先遞迴移動 n−1 個圓盤 → 再移動最大圓盤 → 最後遞迴移動 n−1 個圓盤。
