深度解析遞歸：從理論誤區到漢諾塔的非遞歸實戰

曾見一道經典面試題：「結構化程序設計的三大基礎結構——順序、選擇、循環，是否不可或缺？」答案令人深思：只要擁有遞歸，循環便非必需。以數組求和為例，遞歸寫法如下：

float rsum(float a[], const int n) {
    if (n <= 0) return 0;
    else return rsum(a, n - 1) + a[n - 1];
}

這在邏輯上等價於迴圈累加，但現實中所有語言皆支援循環，卻非皆支援遞歸。遞歸雖具圖靈完備性，但「無遞歸照樣能工作」。令人費解的是，許多開發者明明循環更直觀，卻執意鑽研遞歸，實屬「學究陋習」。

遞歸是演算法嗎？

常見「遞歸演算法」、「非遞歸演算法」之稱，實則遞歸非演算法，而是一種指導思想。若某演算法以遞歸為核心思路，便稱之為遞歸演算法；反之則為非遞歸演算法。凡循環能解之問題，皆有遞歸解，故循環演算法本質上均屬非遞歸範疇。

強調此點非為針鋒相對，而是要指出：編寫何種演算法，關鍵在於你的指導思想。若一開始便想到迭代，卻強行尋找遞歸寫法，即便代碼看似簡潔，因效率低下實則無用；若僅想到遞歸，再用棧手動消除，無非是把系統自動完成的工作親力親為，效率未必提升，甚至可能因實現不當而更差。

階乘與費波那契：被濫用的教科書範例

從排列組合學起，階乘定義為 n! = 1×2×…×n，費波那契數列定義為「前兩項 0、1，後續各項為前兩項之和」。這兩者本質上皆為迭代過程的抽象，而非天然遞歸。然而教科書卻以「定義是遞歸的」為由，強行推導遞歸實現，再轉為迭代，如同 1÷3=0.333…，0.333…×3=0.999… 般繞圈子，徒增心智負擔。

學生看到遞歸階乘從無欽佩之情，唯有困惑。若要講授遞歸，必須用令人信服的例子——非漢諾塔莫屬。

漢諾塔的非遞歸解法：模擬人類正向思維

漢諾塔被視為「只能用遞歸解決」的典型。但我堅信：若問題可用分析法（遞歸）分解，同樣能用綜合法（正向模擬）求解。現實中搬運盤子，人腦不會遞歸推演至底層再回溯——8 個盤子就會「棧溢出」——而是立即決定下一步怎麼搬。

以 7 個盤子為例（6 個時算法正確，7 個才暴露邏輯缺陷），核心在於三大規律：

1. 目標柱交替規律：當前柱頂盤子的目標柱，取決於該柱最底下需移動盤子的目標柱，自下而上交替。
2. 阻塞處理與狀態保存：遇阻礙盤子，保存當前柱資訊（柱號、最底盤子號、目標柱），轉往阻礙盤子所在柱繼續操作。
3. 問題規模遞減與柱子切換：最大盤子入位後，規模減 1，當前柱切換，最底盤子目標柱固定為 C。

完整 C++ 實現見下方代碼。雖邏輯複雜、執行速度較遞歸慢 10 倍，但極具現實意義：它模擬了人類「不逆推、只正向決策」的真實思維。傳說中搬運 64 個盤子的僧人，絕非遞歸至 1 再回溯——那等胡子白長也搬不完——而是像這樣一步步果斷推進。

#include <iostream>
#include <vector>
using namespace std;
class Needle {
public:
    Needle() { a.push_back(100); }
    void push(int n) { a.push_back(n); }
    int top() { return a.back(); }
    int pop() { int n = a.back(); a.pop_back(); return n; }
    int movenum(int n) { int i = 1; while (a[i] > n) i++; return a.size() - i; }
    int size() { return a.size(); }
    int operator[](int n) { return a[n]; }
private:
    vector<int> a;
};
void Hanoi(int n) {
    Needle needle[3], ns;
    int source = 0, target, target_m = 2, disk, m = n;
    for (int i = n; i > 0; i--) needle[0].push(i);
    while (n) {
        if (!m) { source = ns.pop(); target_m = ns.pop(); m = needle[source].movenum(ns.pop()); }
        if (m % 2) target = target_m; else target = 3 - source - target_m;
        if (needle[source].top() < needle[target].top()) {
            disk = needle[source].top(); m--;
            cout << disk << " move " << (char)(source + 0x41) << " to " << (char)(target + 0x41) << endl;
            needle[target].push(needle[source].pop());
            if (disk == n) { source = 1 - source; target_m = 2; m = --n; }
        } else {
            ns.push(needle[source][needle[source].size() - m]);
            ns.push(target_m); ns.push(source);
            m = needle[target].movenum(needle[source].top());
            target_m = 3 - source - target; source = target;
        }
    }
}

這揭示了計算機編程與人類做事邏輯的鴻溝：人腦逆推深度有限、記憶易出錯；計算機擅長深度遞歸、記憶精準。資深程序員之所以高效，正是因為懂得計算機「喜歡怎麼思考」。

迷宮問題：從神話到「靠邊走」策略

迷宮源於希臘神話——忒修斯靠線團殺死牛頭怪並逃出。許多教材誤述為「鋪線探路、死胡同回溯」，實則神話中線團只是「棧」，用於標記歸路，而非探索。迷宮本質是心理測試，考驗人在反覆失敗中能否保持冷靜；對擁有機器級精準記憶的主體而言，迷宮不再「迷」。

但研究「計算機如何走迷宮」仍有教學價值。常規遞歸/回溯法模擬的是「將軍分兵把口」或「單人靠記憶試錯」，均非最優。更妙的是「靠邊走」法則：將通路視為有寬度的區域，始終貼著一側牆壁前進，必能走出出口。此法無需遞歸、無需棧，代碼極簡：

#include <stdio.h>
typedef struct hero {int x,y,face;} HERO;
void set_hero(HERO* h,int x,int y,int face){h->x=x;h->y=y;h->face=face;}
void go(HERO* h){if(h->face%2) h->x+=2-h->face;else h->y+=h->face-1;}
void goleft(HERO* h){if(h->face%2) h->y+=h->face-2;else h->x+=h->face-1;}
void turnleft(HERO* h){h->face=(h->face+3)%4;}
void turnright(HERO* h){h->face=(h->face+1)%4;}
void print_hero(HERO* h, int b) {
    gotoxy(h->x + 1, h->y + 1);
    if (b) {
        switch (h->face) {
            case 0: printf("%c", 24); break;
            case 1: printf("%c", 16); break;
            case 2: printf("%c", 25); break;
            case 3: printf("%c", 27); break;
        }
    } else printf(" ");
}
int maze[10][10] = { ... }; // 迷宮數據
void print_maze() { ... }
int gomaze(HERO* h) {
    HERO t = *h; int i;
    for (i = 0; i < 2; t = *h) {
        print_hero(h, 1); sleep(1); go(&t);
        if (t.x >= 0 && t.x < 10 && t.y >= 0 && t.y < 10 && !maze[t.y][t.x]) {
            print_hero(h, 0); go(h);
            if (h->x == 9 && h->y == 9) return 1; goleft(&t);
            if (h->x == 0 && h->y == 0) i++;
            if (t.x >= 0 && t.x < 10 && t.y >= 0 && t.y < 10 && !maze[t.y][t.x]) turnleft(h);
        } else turnright(h);
    }
    return 0;
}
main() {
    HERO Tom; set_hero(&Tom, 0, 0, 0); clrscr(); print_maze(); gomaze(&Tom);
}

此法在 TC2 可編譯運行，VC6 需用 API 模擬 gotoxy，且 219 號字符在中文系統 32 位控制台無法顯示。但核心思想極具啟發：最簡單的規則往往源於對問題本質最透徹的洞察。

總結：指導思想決定演算法上限

本文未教寫遞歸，反而給出多個非遞歸實現。核心觀點只有一個：能寫出什麼演算法，取決於你對問題的認識深度。初學者盲目追求「漂亮遞歸」，往往削足適履；優秀的遞歸演算法，必建立在對問題透徹理解之上。正如做事：雖今生無法完成偉業，但要為後人鋪路，每一步都要向正確方向邁進，而非原地空想。