Java 遞歸算法：生成回文數字序列（如 4321234）

問題描述

給定正整數 n，遞歸輸出以 n 為中心的回文數字序列。例如 n=4 輸出 4 3 2 1 2 3 4（或連續字串 4321234）。

遞歸思路

回文結構天然適合遞歸：

1. 基準情況：n == 1 時直接輸出 1
2. 遞歸步驟：輸出 n，遞歸處理 n-1，返回後再輸出 n

調用棧展開過程恰好構成「去程遞減、回程遞增」的回文模式。

代碼實現

public class PalindromeRecursion {

    /**
     * 遞歸生成回文並打印，返回當前值供上層打印
     */
    public int printPalindrome(int n) {
        if (n > 1) {
            System.out.print(n);           // 去程：打印當前數
            printPalindrome(n - 1);        // 遞歸深入
        }
        System.out.print(n);               // 回程：再次打印當前數（基準情況 n=1 只執行這行）
        return n;
    }

    public static void main(String[] args) {
        PalindromeRecursion demo = new PalindromeRecursion();
        demo.printPalindrome(10); // 輸出：109876543212345678910
        System.out.println();     // 換行
    }
}

執行流程圖解（以 n=3 為例）

printPalindrome(3)
  ├─ print 3
  ├─ printPalindrome(2)
  │    ├─ print 2
  │    ├─ printPalindrome(1)
  │    │    ├─ print 1  ← 基準情況
  │    │    └─ return 1
  │    ├─ print 2  ← 回程
  │    └─ return 2
  ├─ print 3  ← 回程
  └─ return 3

輸出序列：3 2 1 2 3

變體擴展

返回字符串而非直接打印

public String buildPalindrome(int n) {
    if (n == 1) return "1";
    return n + buildPalindrome(n - 1) + n;
}
// buildPalindrome(4) → "4321234"

字母回文（如 "abcdcba"）

public void printCharPalindrome(char start, char end) {
    if (start > end) return;
    System.out.print(start);
    printCharPalindrome((char)(start + 1), end);
    if (start != end) System.out.print(start); // 中心字符不重複
}
// printCharPalindrome('a', 'd') → a b c d c b a

複雜度分析

• 時間：O(n) —— 每層遞歸常數操作，共 n 層
• 空間：O(n) —— 遞歸棧深度 n（可改寫尾遞歸或迴路優化為 O(1)）

總結

回文生成是遞歸「去程處理、回程收尾」經典模式的教科書級例題。理解調用棧與輸出序列的對應關係，是掌握遞歸思維的關鍵一步。