在 C 語言中,函數可以直接或間接呼叫自己,這種機制稱為「遞迴」。直接遞迴指函數內部直接呼叫自身;間接遞迴則是函數 A 呼叫函數 B,B 再呼叫 A,形成呼叫鏈。本文重點探討直接遞迴。
數學定義:n! = n × (n-1)!,且 0! = 1! = 1。遞迴關係明確,終止條件為 n <= 1。
#include <stdio.h>
long long factorial(int n) {
if (n == 0 || n == 1) return 1; // 終止條件
return n * factorial(n - 1); // 遞迴呼叫
}
int main() {
int m;
printf("請輸入非負整數: ");
scanf("%d", &m);
if (m < 0) {
printf("輸入錯誤!\n");
} else {
printf("%d! = %lld\n", m, factorial(m));
}
return 0;
}
每次呼叫都會在記憶體堆疊區建立新的活化記錄,包含參數、區域變數、返回位址:
factorial(5) 呼叫 factorial(4) → 暫停等待factorial(4) 呼叫 factorial(3) → 暫停等待factorial(1) 返回 12*1=2 → 3*2=6 → 4*6=24 → 5*24=120此過程中,每一層的區域變數 n 獨立存在於不同的堆疊幀中,互不干擾。
| 優點 | 缺點 |
|---|---|
| 程式碼簡潔、邏輯清晰,適合樹、圖、分治等問題 | 每層呼叫消耗堆疊空間,深度過大導致 Stack Overflow |
| 天然符合數學歸納定義 | 函數呼叫開銷大,執行效率通常低於迭代 |
記憶體釋放機制: 當函數執行完畢返回時,系統自動釋放該層堆疊幀,恢復上一層的變數與返回點。
理論上任何遞迴程式都能改寫為迴圈+堆疊的非遞迴形式,但程式碼會變複雜。選擇遞迴還是迭代,取決於可讀性與效能需求的權衡。
遞迴是強大的程式設計工具,核心在於「找出子問題結構」與「設定正確終止條件」。初學者建議從階乘、費波納契、漢諾塔等經典題目入手,並在紙上畫出呼叫堆疊圖,深入理解記憶體與流程變化。