C 語言遞歸練習：計算奇數乘積 1×3×5×...×(2n-1) 的遞歸與迭代實現

編輯：關於C語言

問題描述

編寫函數計算前 n 個奇數的乘積：f(n) = 1 × 3 × 5 × ... × (2n-1)。題目要求遞歸算法，但原代碼給出的是迭代實現，這是一個教學常見的「題目要求與代碼不符」案例，值得深度分析。

原代碼分析：迭代版（非遞歸）

#include <stdio.h>

long fac(int n);  // 函數名誤導：非階乘

int main() {
    int m;
    long result;
    printf("請輸入一個整數(不能太大): ");
    scanf("%d", &m);
    result = fac(m);
    printf("%ld\n", result);
    return 0;
}

long fac(int n) {
    int i;
    int sum = 1;  // 變量名誤導：非求和
    for (i = 1; i <= 2*n-1; i += 2) {
        sum *= i;
    }
    return sum;
}

代碼問題清單

正確遞歸實現


long long odd_product_recursive(int n) {
    if (n <= 0) return 1;           // 基礎情況：空乘積 = 1
    if (n == 1) return 1;           // 1 = 1
    return (2LL * n - 1) * odd_product_recursive(n - 1);
}

// 尾遞歸優化版（編譯器可能優化為迭代）
long long odd_product_tail_recursive(int n, long long acc) {
    if (n <= 0) return acc;
    return odd_product_tail_recursive(n - 1, acc * (2LL * n - 1));
}

// 調用：odd_product_tail_recursive(n, 1);

遞歸 vs 迭代深度對比

問題	原代碼	建議修正
函數名語義錯誤	`fac` 暗示階乘	`odd_product` 或 `double_factorial`
變量名語義錯誤	`sum` 暗示加法	`product` 或 `result`
類型不匹配風險	`int sum` 但返回 `long`	統一用 `long long`
未滿足題目要求	迭代實現	需提供遞歸版本

數學背景：雙階乘

此乘積即雙階乘：(2n-1)!! = 1 × 3 × 5 × ... × (2n-1)。性質：

(2n-1)!! = (2n)! / (2^n n!)
組合意義：2n 個元素分成 n 個無序配對的方案數
近似：(2n-1)!! ~ √2 (2n/e)^n（斯特林公式推導）

溢出邊界分析

維度	遞歸	迭代
代碼簡潔度	高（數學定義直接翻譯）	中
空間複雜度	O(n) 棧幀	O(1)
溢出風險	棧溢出 (n 大時)	無棧風險
性能	函數調用開銷	極快
可讀性	符合數學歸納直覺	需理解循環不變量

建議：生產代碼必須用 unsigned long long 並檢查溢出，或引入大整數庫。

綜合工程版：遞歸+迭代雙實現+溢出檢測


#include <stdio.h>
#include <limits.h>

unsigned long long odd_product_iter(int n) {
    unsigned long long prod = 1;
    for (int i = 1; i <= n; i++) {
        unsigned long long term = 2ULL * i - 1;
        if (prod > ULLONG_MAX / term) {
            fprintf(stderr, "溢出於 n=%d\n", i);
            return 0;
        }
        prod *= term;
    }
    return prod;
}

unsigned long long odd_product_rec(int n) {
    if (n <= 0) return 1;
    unsigned long long prev = odd_product_rec(n - 1);
    unsigned long long term = 2ULL * n - 1;
    if (prev && prev > ULLONG_MAX / term) {
        fprintf(stderr, "遞歸溢出於 n=%d\n", n);
        return 0;
    }
    return prev * term;
}

int main() {
    int n;
    printf("輸入 n (1-10 建議): ");
    if (scanf("%d", &n) == 1 && n > 0) {
        printf("迭代: %llu\n", odd_product_iter(n));
        printf("遞歸: %llu\n", odd_product_rec(n));
    }
    return 0;
}