本文展示一個純 C 遞歸函數查找數組最大值，雖邏輯正確但存在嚴重效率與語法問題，作為遞歸教學反面教材，並給出正確遞歸寫法與迭代最優解。
// 原文問題代碼
int Getmax(int arr[n]) { // 錯誤：n 未定義，VLA 參數非標準 C
for (int i = 0; i < n; i++) { // 循環與遞歸混淆
if (n == 0) return arr[0];
else {
arr[0] = arr[0] > Getmax(arr[]+1, n-1) ? arr[0] : Getmax(arr[]+1, n-1); // 重複遞歸、語法錯誤
return arr[0];
}
}
}
致命缺陷：
n 未聲明，arr[]+1 非法語法。for 循環內調用遞歸導致指數級爆炸：每層調用兩次遞歸，時間 O(2^N)。arr[0] 有副作用。int max_recursive(const int *arr, int n) {
if (n == 1) return arr[0]; // 基線條件
int max_rest = max_recursive(arr+1, n-1); // 遞歸求剩餘最大值
return (arr[0] > max_rest) ? arr[0] : max_rest; // 合併
}
時間 O(N)，空間 O(N)（棧深度），不修改原數組。
int max_iterative(const int *arr, int n) {
int maxv = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > maxv) maxv = arr[i];
return maxv;
}
時間 O(N)，空間 O(1)，無函數調用開銷，編譯器易優化（向量化、循環展開）。
| 場景 | 推薦 | 理由 |
|---|---|---|
| 線性掃描（最大值、求和、計數） | 迭代 | 尾遞歸無優勢，迭代零開銷 |
| 樹/圖遍歷、分治（快排、歸併、二分） | 遞歸 | 天然匹配數學定義，代碼簡潔 |
| 動態規劃（自頂向下記憶化） | 遞歸 | 狀態轉移直觀 |
| 極大數據量（N > 10^5） | 迭代 | 避免棧溢出 |
遞歸是強大工具，但**線性問題用遞歸屬於濫用**。正確遞歸寫法應「單次遞歸調用 + 合併結果」，而非循環套遞歸。工程中優先迭代，複雜結構問題才用遞歸，並注意棧深度限制（可用 -Wframe-larger-than 檢測）。
