C語言遞歸函數精髓：階乘計算與漢諾塔問題完整實現

遞歸調用核心概念

函數在函數體內調用自身稱為遞歸調用。必須設置終止條件，否則無限遞歸導致棧溢出。常用條件判斷：滿足條件不再遞歸，逐層返回。

經典例題 1：遞歸計算階乘

數學定義：

n! = 1          (n=0,1)
n! = n × (n-1)! (n>1)

代碼實現：

long ff(int n) {
    long f;
    if (n < 0) printf("n<0, input error");
    else if (n==0 || n==1) f = 1;
    else f = ff(n-1) * n;
    return f;
}

int main() {
    int n; long y;
    scanf("%d", &n);
    y = ff(n);
    printf("%d!=%ld", n, y);
    return 0;
}

執行流程（以 n=5 為例）：

1. 主調 ff(5) → 進入 ff
2. n=5 不滿足基本情況 → 遞歸 ff(4)
3. 依次遞歸至 ff(1) 返回 1
4. 逐層回溯：ff(2)=2、ff(3)=6、ff(4)=24、ff(5)=120

遞推法（迭代）更易理解，但某些問題（如漢諾塔）必須用遞歸。

經典例題 2：漢諾塔問題

規則：三根針 A/B/C，A 上 n 個盤（大下小上），借助 B 移至 C，每次移一盤，大盤不得壓小盤。

遞歸策略：

• n=1：直接 A→C
• n≥2 分三步：
  1. 將 n-1 個盤 A→B（借助 C）
  2. 將第 n 個盤 A→C
  3. 將 n-1 個盤 B→C（借助 A）

代碼實現：

void move(int n, char x, char y, char z) {
    if (n == 1)
        printf("%c-->%c\n", x, z);
    else {
        move(n-1, x, z, y);  // n-1: x→y (借助 z)
        printf("%c-->%c\n", x, z);  // 第 n 個: x→z
        move(n-1, y, x, z);  // n-1: y→z (借助 x)
    }
}

int main() {
    int h;
    scanf("%d", &h);
    printf("the step to moving %2d diskes:\n", h);
    move(h, 'a', 'b', 'c');
    return 0;
}

n=4 運行輸出：

a-->b
a-->c
b-->c
a-->b
c-->a
c-->b
a-->b
a-->c
b-->c
b-->a
c-->a
b-->c
a-->b
a-->c
b-->c

變量作用域引入

形參僅在調用期間分配內存，調用結束即釋放，說明形參作用域限於函數內。C 語言所有量皆有作用域，按範圍分：

• 局部變量：函數/塊內定義，僅在塊內有效
• 全局變量：函數外定義，整個文件/項目可見

聲明方式不同，作用域不同，後續章節詳細展開。