C語言遞歸求素數：教學示例與性能陷阱

代碼展示

// 遞歸求素數
// by winxos 2011-08-29
#include <stdio.h>
// #include <math.h>

int isdiv(int a, int b)
{
    // if (b == (int)sqrt(a) + 1) return 0; // 快但不優雅
    if (b == a - 1) return 0;
    if (a % b == 0) return 1;
    return isdiv(a, b + 1); // 缺少 return，原代碼有 Bug
}

int isprime(int n)
{
    if (n < 2) return 0;
    if (n == 2) return 1;
    return !isdiv(n, 2);
}

int main()
{
    for (int i = 1; i < 10000; ++i) {
        if (isprime(i))
            printf("%d ", i);
    }
    return 0;
}

關鍵問題分析

1. 遞歸深度過大：isdiv 從 2 遞歸到 n-1，對 n=10000 深度近萬，極易棧溢出。
2. 缺少返回值：原代碼 isdiv(a, b+1); 未 return，導致未定義行為（現已修正）。
3. 算法複雜度：O(n) 試除法，遠慢於 √n 試除或篩法。
4. 註釋掉的優化：b == (int)sqrt(a)+1 可將遞歸深度降至 √n，但作者稱「不優雅」而放棄。

改進版：尾遞歸 + √n 剪枝

int isdiv_opt(int a, int b)
{
    if (b * b > a) return 0;      // √n 剪枝
    if (a % b == 0) return 1;
    return isdiv_opt(a, b + 1);   // 尾遞歸，編譯器可優化為迭代
}

int isprime_opt(int n)
{
    if (n < 2) return 0;
    if (n == 2) return 1;
    if (n % 2 == 0) return 0;     // 排除偶數
    return !isdiv_opt(n, 3);      // 從 3 開始，步長 2
}

配合 -O2 編譯，尾遞歸會被優化為循環，棧深度恆為 O(1)。

工程級素數判定建議

• 小範圍批量：埃拉托斯特尼篩（Sieve of Eratosthenes）O(n log log n) 預計算。
• 單次大數：Miller-Rabin 概率檢測（確定性版本對 64 位整數僅需測試 12 個基數）。
• 教學用途：遞歸版僅適合極小數值（< 1000）演示遞歸概念，切勿用於生產。

總結

原代碼展示了遞歸思維，但存在棧溢出、缺返回值、複雜度高等多重問題。工程實踐中，正確性 > 優雅 > 性能，請優先選擇成熟算法與庫函數。