C語言超複雜間接遞歸案例：素數查找與優化陷阱深度分析

問題背景

原文展示一個極其複雜的間接遞歸程式：輸入整數 X，輸出最接近 X 的素數（X 本身為素則輸出 X；兩側等距取較大者）。作者以此批判初學者濫用遞歸、忽略效能、混淆邏輯的惡習。

核心邏輯重構

// 簡化版：迭代試除法 + 素數表緩存
#include <stdio.h>
#include <stdbool.h>
#include <math.h>

#define MAX_PRIME 1000000
int primes[MAX_PRIME], prime_cnt = 0;

bool is_prime(int x) {
    if (x < 2) return false;
    for (int i = 0; i < prime_cnt && primes[i] * (long long)primes[i] <= x; i++)
        if (x % primes[i] == 0) return false;
    return true;
}

void ensure_primes_up_to(int limit) {
    for (int n = (prime_cnt ? primes[prime_cnt-1]+1 : 2); n <= limit; n++)
        if (is_prime(n)) primes[prime_cnt++] = n;
}

int nearest_prime(int x) {
    if (x <= 2) return 2;
    int limit = (int)sqrt(x) + 100; // 稍微擴大
    ensure_primes_up_to(limit);
    if (is_prime(x)) return x;
    for (int d = 1; ; d++) {
        int low = x - d, high = x + d;
        bool low_ok = (low >= 2 && is_prime(low));
        bool high_ok = is_prime(high);
        if (low_ok && high_ok) return high; // 等距取大
        if (high_ok) return high;
        if (low_ok) return low;
    }
}

int main() {
    int n, x;
    scanf("%d", &n);
    while (n--) { scanf("%d", &x); printf("%d\n", nearest_prime(x)); }
    return 0;
}

原始碼主要問題

1. 間接遞歸地獄：get_nearest → be_prime → get_remainder → add_1_prime → be_prime → ...，呼叫鏈極深、極難追蹤。
2. 重複計算：每次判斷素數都從頭建立素數表，未緩存。
3. 資料結構濫用：鏈表存素數，查找 O(n)；陣列或位圖可 O(1) 存取。
4. 記憶體洩漏：my_malloc 分配節點從未 free。
5. 基礎情況錯誤：x <= 1、x == 2 處理混亂。

優化版效能對比 (10⁹ 內測試)

教訓總結

• 遞歸非萬能，迭代 + 緩存 往往更簡潔高效。
• 素數判斷：小數試除、大數米勒-拉賓、批量查詢預計算篩法。
• 資料結構選型：素數表用動態陣列，支援 push_back 與隨機存取。
• 代碼可讀性第一：單一職責函數、清晰命名、避免過度抽象。

這個反面教材極具警示意義：追求「聰明」的遞歸技巧往往產生不可維護、效能低下的代碼；工程上應優先選擇清晰、可驗證、可優化的演算法與資料結構。