漢諾塔問題：C 語言遞歸與匯編語言棧實現對比

漢諾塔：從遞歸到棧的底層實現

漢諾塔是經典的遞歸問題。本文對比 C 語言遞歸解法與 x86 匯編語言手動管理棧的實現，揭示函數調用的本質。

問題規則回顧

• 三根柱子：X (源)、Y (輔助)、Z (目標)。
• n 個盤子從小到大疊在 X 上。
• 每次移動一個盤子，大盤不能壓小盤。
• 目標：將所有盤子移至 Z，保持順序。

C 語言遞歸解法 (高層邏輯)

void move(char from, char to) {
    printf("%c-->%c ", from, to);
}

void hanoi(int n, char from, char aux, char to) {
    if (n == 1) {
        move(from, to);           // 基例：直接移動
    } else {
        hanoi(n-1, from, to, aux); // 步驟1: 將 n-1 個從 from 移到 aux (借用 to)
        move(from, to);            // 步驟2: 將第 n 個(最大)從 from 移到 to
        hanoi(n-1, aux, from, to); // 步驟3: 將 n-1 個從 aux 移到 to (借用 from)
    }
}

int main() {
    hanoi(3, 'X', 'Y', 'Z'); // 3 階漢諾塔
    return 0;
}

遞歸本質：每層調用將問題分解為兩個子問題 + 一個基本操作。編譯器自動管理調用棧（保存返回地址、參數、局部變量）。

x86 匯編實現 (手動棧管理)

核心思想：用棧模擬遞歸調用。棧幀結構：[返回地址] [n] [from] [aux] [to]。使用 BP 作為幀指針訪問參數。

; 關鍵數據段
DATA SEGMENT
    n       DB  ?
    msg     DB  'Enter n: $'
    msg1    DB  'HANOI Moves: $'
    arrow   DB  '-->$'
    count   DW  0
DATA ENDS

CODE SEGMENT
    ASSUME CS:CODE, DS:DATA
START:
    ; 初始化 DS, 輸入 n, 設置參數壓棧 (to, aux, from, n)
    ; 調用 HANOI_MOVE
    ; ...

HANOI_MOVE PROC NEAR
    MOV BP, SP           ; 保存棧幀基址
    MOV AX, [BP+8]       ; 取參數 n (假設棧布局: 返回地址, n, from, aux, to)
    CMP AX, 1
    JG MORE_THAN_ONE     ; n > 1 跳轉

    ; === 基例 n == 1 ===
    CALL PRINT_STEP      ; 打印步驟號 [1] [2] ...
    MOV DX, [BP+4]       ; 取 from
    CALL PRINT_CHAR
    LEA DX, arrow
    CALL PRINT_STR
    MOV DX, [BP+10]      ; 取 to
    CALL PRINT_CHAR
    CALL PRINT_SPACE
    RET                  ; 返回

MORE_THAN_ONE:
    ; === 遞歸步驟 1: hanoi(n-1, from, to, aux) ===
    ; 參數入棧順序: aux, to, from, n-1 (逆序壓棧)
    MOV AX, [BP+4]       ; from
    MOV BX, [BP+6]       ; aux
    MOV CX, [BP+8]       ; to
    MOV DX, [BP+10]      ; n
    DEC DX               ; n-1
    PUSH DX              ; n-1
    PUSH BX              ; aux (新 to)
    PUSH CX              ; to (新 aux)
    PUSH AX              ; from
    CALL HANOI_MOVE
    ADD SP, 8            ; 清理棧參數

    ; === 步驟 2: move(from, to) ===
    CALL PRINT_STEP
    MOV DX, [BP+4]       ; from
    CALL PRINT_CHAR
    LEA DX, arrow
    CALL PRINT_STR
    MOV DX, [BP+10]      ; to
    CALL PRINT_CHAR
    CALL PRINT_SPACE

    ; === 遞歸步驟 3: hanoi(n-1, aux, from, to) ===
    MOV AX, [BP+4]       ; from
    MOV BX, [BP+6]       ; aux
    MOV CX, [BP+8]       ; to
    MOV DX, [BP+10]      ; n
    DEC DX               ; n-1
    PUSH DX              ; n-1
    PUSH CX              ; to (新 to)
    PUSH AX              ; from (新 aux)
    PUSH BX              ; aux (新 from)
    CALL HANOI_MOVE
    ADD SP, 8

    RET
HANOI_MOVE ENDP

; ... PRINT_STEP, PRINT_CHAR, PRINT_STR, PRINT_SPACE 等輔助子程序 ...

CODE ENDS
END START

關鍵對比總結

核心感悟

遞歸在高級語言中是「語法糖」，底層全靠棧支撐。理解匯編實現有助於掌握：

1. 函數調用開銷（棧幀構建/銷毀）。
2. 遞歸深度受限於棧大小（棧溢出風險）。
3. 尾遞歸優化原理（複用當前棧幀）。

現代開發中極少手寫匯編遞歸，但調試崩潰、分析棧追蹤、編寫編譯器/運行時時，這些知識不可或缺。

1. 上一篇文章： C 語言求解 4×4 矩陣最大最小值及主對角線元素和
2. 下一篇文章： CSAPP 2.12 習題解析：位運算提取與修改最低有效字節

關於C語言

C# 6 種常用集合類詳解 (一)

陣列的不足與集合的優勢 陣列限制集合優勢 固定大小，

C語言數據結構與算法實戰：二叉樹、哈夫曼編碼、圖的遍歷

C語言數據結構與算法實戰：二叉樹、哈夫曼編碼、圖的遍歷 本文

C 語言字串反轉完全指南：從整數陣列到字串的演算法優化之路

整數陣列反轉：基礎邏輯建立 對 {1,2,3,4,5} 反轉

C語言堆棧佈局揭秘：為什麼2+2能等於5？指針算術與內存對齊深度解析

看似荒謬的「2+2=5」：C語言指針算術與棧佈局的隱藏邏輯