Java 計算任意位數水仙花數（迴文數）遞迴演算法實作

題目釐清：水仙花數 vs 迴文數

原標題混淆兩個概念：

• 水仙花數：N 位數，各位數字的 N 次方和等於自身（如 153 = 1³+5³+3³）。
• 迴文數：正讀反讀相同（如 121、12321、123321）。

提供的程式碼實際生成的是迴文數，本文以此為主並修正術語。

遞迴生成迴文數演算法

核心思路：從外層向內層遞迴構建對稱結構。對於長度 len：

• 若 len == 1：輸出 1~9。
• 若 len == 2：輸出 11, 22, ..., 99。
• 若 len > 2：外層選 1~9，內層遞迴生成長度 len-2 的迴文，再鏡像外層。

完整程式碼

public class PalindromeGenerator {

    public static void main(String[] args) {
        int maxLen = 6; // 產生 1~6 位數迴文數
        for (int len = 1; len <= maxLen; len++) {
            System.out.println("=== " + len + " 位數迴文數 ===");
            generate(len).forEach(System.out::println);
        }
    }

    /** 產生指定長度的所有迴文數（不含前導零） */
    public static List<String> generate(int len) {
        List<String> result = new ArrayList<>();
        if (len <= 0) return result;

        char[] buffer = new char[len];
        build(buffer, 0, len - 1, result);
        return result;
    }

    private static void build(char[] buf, int left, int right, List<String> out) {
        if (left > right) {
            out.add(new String(buf));
            return;
        }
        if (left == right) { // 奇數長度，中間位
            for (char c = '0'; c <= '9'; c++) {
                buf[left] = c;
                out.add(new String(buf));
            }
            return;
        }

        // 雙邊對稱填入
        for (char c = (left == 0 ? '1' : '0'); c <= '9'; c++) {
            buf[left] = c;
            buf[right] = c;
            build(buf, left + 1, right - 1, out);
        }
    }
}

輸出範例（前 20 個）

=== 1 位數迴文數 ===
1 2 3 4 5 6 7 8 9
=== 2 位數迴文數 ===
11 22 33 44 55 66 77 88 99
=== 3 位數迴文數 ===
101 111 121 131 141 151 161 171 181 191
202 212 ... 999
=== 4 位數迴文數 ===
1001 1111 1221 1331 ... 9999

複雜度分析

• 時間：O(9 × 10^{⌊(n-1)/2⌋}) — 即迴文數總數，最優。
• 空間：O(n) 遞迴深度 + O(結果集大小)。

補充：真正的水仙花數計算

public static List<Integer> narcissistic(int digits) {
    List<Integer> res = new ArrayList<>();
    int start = (int) Math.pow(10, digits - 1);
    int end = (int) Math.pow(10, digits);
    int[] pow = new int[10];
    for (int i = 0; i < 10; i++) pow[i] = (int) Math.pow(i, digits);

    for (int n = start; n < end; n++) {
        int sum = 0, t = n;
        while (t > 0) { sum += pow[t % 10]; t /= 10; }
        if (sum == n) res.add(n);
    }
    return res;
}
// 3 位數：153, 370, 371, 407
// 4 位數：1634, 8208, 9474

擴展：大整數迴文數（BigInteger）

若需超過 long 範圍，直接用字串操作或 BigInteger，遞迴邏輯不變。