遞歸計算厄密多項式 H_n(x)：C語言數學遞歸實戰

遞歸計算厄密多項式 H_n(x)：C語言數學遞歸實戰

厄密多項式定義：
H_0(x) = 1
H_1(x) = 2x
H_n(x) = 2x·H_{n-1}(x) - 2(n-1)·H_{n-2}(x) (n≥2)

遞歸實現

#include <stdio.h>

int hermite(int n, int x) {
    if (n <= 0) return 1;
    if (n == 1) return 2 * x;
    return 2 * x * hermite(n-1, x) - 2 * (n-1) * hermite(n-2, x);
}

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

驗證示例

H_3(2) = 2*2*H_2(2) - 2*2*H_1(2)
H_2(2) = 2*2*H_1(2) - 2*1*H_0(2) = 4*4 - 2*1 = 14
H_1(2) = 4
H_3(2) = 4*14 - 4*4 = 56 - 16 = 40  ✓

性能備註

• 純遞歸存在重複子問題，時間複雜度指數級。
• 實際工程中應用**記憶化遞歸**或**動態規劃**（自底向上）將複雜度降至 O(n)。
• 本題作為教學示例展示數學遞歸直接轉代碼的直觀性。

厄密多項式在量子諧振子、概率論、數值分析中有重要應用，遞歸定義是其核心計算方式之一。