C/C++ 遞歸算法詳解：階乘與漢諾塔經典案例

遞歸核心概念

遞歸是指函數直接或間接調用自身的過程。三大特點：

1. 函數內部調用自身
2. 必須有明確的遞歸出口（終止條件）
3. 代碼簡潔但效率較低，深度過大易導致棧溢出

遞歸分類

• 直接遞歸：函數直接調用自身
• 間接遞歸：A 調用 B，B 調用 A（需前向聲明）或嵌套調用

經典例題 1：階乘計算

int recursive(int i) {
    int sum = 0;
    if (0 == i) return 1;
    else sum = i * recursive(i - 1);
    return sum;
}

簡潔明了，但大數階乘易溢出且效率低，工程中常用迭代或查表優化。

經典例題 2：漢諾塔問題

問題描述

三根柱子，第一根有 64 個盤子（小上大下）。要求移至第三根，規則：每次移一個，小盤必在大盤上。

遞歸思維分解（和尚喻義）

第 1 個和尚想：找人移 63 個到第 2 柱 → 自己移第 64 個到第 3 柱 → 找人移 63 個從第 2 柱到第 3 柱。
第 2 個和尚同理分解 62 個… 遞推至第 64 個和尚（只需移 1 個，即遞歸出口）。

3 個盤子移動演示

1→3, 1→2, 3→2  (借助第 3 柱移 2 個到第 2 柱)
1→3              (移第 3 個到第 3 柱)
2→1, 2→3, 1→3  (借助第 1 柱移 2 個從第 2 柱到第 3 柱)
共 7 步 = 2³ - 1

通用遞歸公式

移動 n 個盤子從 A 到 C（借助 B）：

1. hanoi(n-1, A, C, B) // 移 n-1 從 A 到 B
2. move(n, A, C) // 移第 n 個從 A 到 C
3. hanoi(n-1, B, A, C) // 移 n-1 從 B 到 C

C 語言實現

#include <stdio.h>

void move(int n, char a, char b) {
    printf("Move disk %d from %c to %c\n", n, a, b);
}

void hanoi(int n, char a, char b, char c) {
    if (n == 1) move(1, a, c);
    else {
        hanoi(n-1, a, c, b);
        move(n, a, c);
        hanoi(n-1, b, a, c);
    }
}

int main() {
    int num;
    scanf("%d", &num);
    hanoi(num, 'A', 'B', 'C');
    return 0;
}

步數規律與複雜度

• 移動 n 個盤子步數 = 2ⁿ - 1
• 時間複雜度 O(2ⁿ)，空間複雜度 O(n)（遞歸棧深度）
• 64 個盤子需 2⁶⁴-1 步，按 1 秒/步 需 5840 億年

遞歸優缺點總結

遞歸是算法設計的核心思想之一，掌握「分解子問題 → 找到出口 → 合併結果」的思維模式，對解決複雜問題至關重要。