經典遞歸算法實戰：斐波那契數列與漢諾塔問題 C 語言實現

1. 斐波那契數列

定義：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)。

int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibonacci(n-1) + fibonacci(n-2);
}

缺點：遞歸樹指數級重複計算，時間 O(2^n)。實際工程用迭代/矩陣快速冪/備忘錄優化至 O(n) 或 O(log n)。

2. 漢諾塔

規則：三根柱 A、B、C。將 N 個盤子從 A 移至 C，借助 B。每次移一盤，大盤不得置於小盤上。

遞歸策略

1. 將上方 N-1 個盤從 A 移至 B（借助 C）。
2. 將第 N 個盤從 A 移至 C。
3. 將 N-1 個盤從 B 移至 C（借助 A）。

參數順序：hanoi(n, from, aux, to)。

代碼實現

void hanoi(int n, int from, int aux, int to) {
    if (n == 1) {
        printf("%d -> %d\n", from, to);
        return;
    }
    hanoi(n-1, from, to, aux);   // 步驟1
    printf("%d -> %d\n", from, to); // 步驟2
    hanoi(n-1, aux, from, to);   // 步驟3
}

3. 運行演示

N=3

1 -> 3
1 -> 2
3 -> 2
1 -> 3
2 -> 1
2 -> 3
1 -> 3

N=4

共 15 步（2^4-1），輸出略。

4. 遞歸深度與調用次數

• 移動次數：2^n - 1。
• 遞歸調用次數：2^(n+1) - 1（含葉子節點打印）。
• 最大遞歸深度：N（棧空間 O(N)）。

5. 完整主程序

#include <stdio.h>

int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibonacci(n-1) + fibonacci(n-2);
}

void hanoi(int n, int from, int aux, int to) {
    if (n == 1) { printf("%d -> %d\n", from, to); return; }
    hanoi(n-1, from, to, aux);
    printf("%d -> %d\n", from, to);
    hanoi(n-1, aux, from, to);
}

int main() {
    printf("Fibonacci(8) = %d\n", fibonacci(8)); // 21
    printf("\nHanoi 3 disks:\n");
    hanoi(3, 1, 2, 3);
    return 0;
}

總結

• 斐波那契展示遞歸定義直觀但效率低，引出動態規劃/矩陣優化思路。
• 漢諾塔是「分治+遞歸」教科書級範例，參數角色（源、輔、目）在遞歸中輪換是關鍵理解點。
• 兩題均體現遞歸三要素：**終止條件**、**問題分解**、**狀態傳遞**。