C語言遞歸實現楊輝三角（帕斯卡三角形）完整代碼與原理

楊輝三角數學定義

• 第 n 行（從 0 開始）有 n+1 個數。
• 首尾為 1：C(n, 0) = C(n, n) = 1。
• 中間數 = 上一行左右兩數之和：C(n, k) = C(n-1, k-1) + C(n-1, k)。
• 即二項式系數：C(n, k) = n! / (k! (n-k)!)。

遞歸函數實現

// 計算第 n 行第 k 個數 (k 從 1 開始，對應 C(n, k-1))
int C(int n, int k) {
    if (k == 1 || k == n + 1)  // 首尾為 1
        return 1;
    return C(n - 1, k - 1) + C(n - 1, k); // 遞歸定義
}

主程序：打印等腰三角形

#include <stdio.h>

int C(int n, int k); // 前置聲明

int main() {
    int i, j, n;
    printf("請輸入行數 n: ");
    scanf("%d", &n);

    for (i = 0; i <= n; i++) {          // 控制行號 0~n
        // 打印前導空格，實現居中
        // 假設每個數佔 4 字符寬度 (%4d)，最後一行有 n+1 個數
        // 總寬度約 4*(n+1)，當前行 i+1 個數，寬度 4*(i+1)
        // 空格數 = (總寬 - 當前寬) / 2 / 字符寬度(這裡按字符計算)
        // 原代碼用 20-2*i 經驗值，針對 n=9 時約對齊
        for (j = 1; j <= 20 - 2 * i; j++)
            printf(" ");

        // 打印當前行數字
        for (j = 1; j <= i + 1; j++)    // 第 i 行有 i+1 個數
            printf("%4d", C(i, j));     // %4d 固定寬度右對齊

        printf("\n");
    }
    return 0;
}

int C(int n, int k) {
    if (k == 1 || k == n + 1)
        return 1;
    return C(n - 1, k - 1) + C(n - 1, k);
}

運行效果示例 (n=5)

                    1
                  1   1
                1   2   1
              1   3   3   1
            1   4   6   4   1
          1   5  10  10   5   1

遞歸方案的性能缺陷與優化

❌ 指數級重複計算

遞歸樹中大量子問題重疊（如 C(4,2) 會多次計算 C(3,1)、C(3,2)）。時間複雜度 ~ O(2^n)，**n>20 極慢**。

✅ 優化方案一：動態規劃 / 迭代構建（推薦生產環境）

void printYanghuiIter(int n) {
    int **a = (int**)malloc((n+1) * sizeof(int*));
    for (int i = 0; i <= n; i++) {
        a[i] = (int*)malloc((i+1) * sizeof(int));
        a[i][0] = a[i][i] = 1; // 首尾 1
        for (int j = 1; j < i; j++)
            a[i][j] = a[i-1][j-1] + a[i-1][j]; // 自底向上填表
    }
    // 打印邏輯同前...
    // 釋放內存...
}

• 時間 O(n^2)，空間 O(n^2)（可優化到 O(n) 滾動數組）。

✅ 優化方案二：遞歸 + 備忘錄（自頂向下 DP）

int memo[100][100] = {0}; // 假設 n<100
int C_memo(int n, int k) {
    if (k == 1 || k == n + 1) return 1;
    if (memo[n][k]) return memo[n][k];
    return memo[n][k] = C_memo(n-1, k-1) + C_memo(n-1, k);
}

• 時間 O(n^2)，空間 O(n^2)，保留遞歸結構。

✅ 優化方案三：組合數公式直接計算（單個值 O(k)）

long long C_comb(int n, int k) { // k 從 0 開始
    if (k > n - k) k = n - k;
    long long res = 1;
    for (int i = 1; i <= k; i++)
        res = res * (n - k + i) / i; // 先乘後除保證整除
    return res;
}

• 無需存儲整個三角形，適合只需某行某值場景。注意溢出（用 long long 或大整數庫）。

空格對齊通用公式

若每個數佔 W 字符（如 %4d → W=4），最後一行 n+1 個數：

// 第 i 行 (0-index) 前導空格字符數：
int spaces = ( (n - i) * W ) / 2;  // 近似，視字體比例微調
for (int s = 0; s < spaces; s++) putchar(' ');

總結

遞歸實現楊輝三角**代碼極簡、直觀體現數學定義**，適合教學演示、小規模 n（<15）。生產環境或大 n **必須用迭代 DP 或組合公式**，避免指數級爆炸。掌握「遞歸定義 → 遞歸代碼 → 重複子問題識別 → DP/備忘錄優化」完整思維鏈路，是算法進階核心技能。