遞歸是函數直接或間接調用自身的編程技巧。本文以階乘、漢諾塔為例,深度剖析遞歸的三要素、調用棧演變、內存佈局、終止條件設計、常見棧溢出原因,並展示遞歸轉迭代的通用方法。
n! = n × (n-1)!)。n → n-1)。n==0 或 1 返回 1)。n!
long long factorial(int n) {
if (n < 0) return -1; // 錯誤碼
if (n == 0 || n == 1) return 1; // 終止條件
return n * factorial(n - 1); // 遞歸推進
}
factorial(5)
main() → factorial(5)
→ 5 * factorial(4)
→ 4 * factorial(3)
→ 3 * factorial(2)
→ 2 * factorial(1)
→ 返回 1
→ 返回 2*1 = 2
→ 返回 3*2 = 6
→ 返回 4*6 = 24
→ 返回 5*24 = 120
每層調用分配**棧幀**:返回地址、參數 n、局部變量、保存的寄存器。n 每層獨立,互不干擾。
long long fact_iter(int n) {
long long r = 1;
for (int i = 2; i <= n; i++) r *= i;
return r;
}
迭代版 O(1) 空間,遞歸版 O(n) 棧空間。n > 10^5 時遞歸將棧溢出。
問題:三根柱 A/B/C,A 上有 n 個盤(大底小頂),借助 B 將所有盤移至 C,每次移一盤,大盤不得壓小盤。
void hanoi(int n, char from, char aux, char to) {
if (n == 1) {
printf("%c --> %c\n", from, to);
return;
}
hanoi(n-1, from, to, aux); // 步驟 1
printf("%c --> %c\n", from, to); // 步驟 2
hanoi(n-1, aux, from, to); // 步驟 3
}
移動次數 2^n - 1,時間複雜度指數級,n=64 時約 1.8×10^19 步,純理論模型。
StackOverflow/段錯誤。
long long fact_tail(int n, long long acc) {
if (n == 0) return acc;
return fact_tail(n-1, n*acc); // 尾調用
}
| 場景 | 推薦 | 理由 |
|---|---|---|
| 樹/圖遍歷、分治、回溯 | 遞歸 | 代碼極度簡潔,邏輯天然匹配 |
| 深度可控 < 1000 | 遞歸可接受 | 棧空間足夠 |
| 深度未知/極大、高性能要求 | 迭代/顯式棧 | 避免棧溢出、消除函數調用開銷 |
| 重疊子問題 | DP/備忘錄 | 避免指數級重複計算 |