極短 C 程式實現大數乘法：遞歸與位運算的巧妙結合

極短 C 程式實現大數乘法：遞歸與位運算的巧妙結合

這是一個僅 196 位元組的 C 程式，能計算超長整數乘法。它不使用額外陣列存儲中間結果，而是巧妙利用遞歸在呼叫堆疊上完成進位傳播，展示了「代碼高爾夫」的極致技巧。

核心程式碼

#include <stdio.h>
char s[99], t[99];
int m, n;
void r(int i, int c) {
    int j = 0, k = i;
    while (k) c += s[j++] * t[k-- - 1];
    if (i) r(i - 1, c / 10);
    printf("%d", c % 10);
}
void main() {
    gets(s); gets(t);
    while (s[n]) s[n++] -= 48;
    while (t[m]) t[m++] -= 48;
    r(m + n - 1, 0);
}

運作原理解析

1. 輸入轉換：將字串字元 '0'~'9' 轉為數值 0~9（減去 ASCII 48）。
2. 遞歸乘法：函式 r(i, c) 計算第 i 位的乘積加進位 c。迴圈 while(k) 實現 s[0]*t[i-1] + s[1]*t[i-2] + ... 的卷積求和。
3. 進位傳播：遞歸呼叫 r(i-1, c/10) 先處理高位，返回時 printf("%d", c%10) 輸出低位，自然完成大數輸出順序。

極致精簡的程式設計技巧

• 全域變數隱式初始化：m, n 自動為 0，省去初始化語句。
• 指標與下標融合：s[j++] * t[k-- -1] 一行完成陣列遍歷與索引運算。
• 遞歸替代迴圈與陣列：利用呼叫堆疊保存中間狀態，避免額外儲存空間。
• 條件判斷簡化：if(i) 取代 if(i>=0)，利用 0 為假特性。

⚠️ 僅供學習參考，切勿用於生產環境

此類代碼極難閱讀、維護，且使用 gets 存在緩衝區溢位風險。實際開發中請使用成熟的大數庫（如 GMP）或清晰的演算法實現。