递归算法实战：汉诺塔与链表操作及快速幂详解

递归是算法设计中极具魅力的思想，通过自顶向下的拆解与自底向上的合并，能将复杂问题转化为结构相同的子问题。本文选取五个经典案例，从汉诺塔的分治策略到链表的指针操作，再到快速幂的指数优化，带你深入理解递归的核心逻辑与代码实现。

1. 汉诺塔问题

汉诺塔是递归最直观的应用场景。将 n 个盘子从 A 柱移到 C 柱（B 为辅助），核心在于将其拆分为三个步骤：首先将上面 n-1 个盘子从 A 移到 B，接着将最大的盘子从 A 直接移到 C，最后将 B 上的 n-1 个盘子移到 C。这两个子问题与原问题完全一致，只是盘子数量和柱子角色发生了变化。

每一层递归只负责当前盘子的移动规划：先递归处理上层，腾出空间给底层最大盘，执行移动后再递归处理剩余部分。当 n=1 时，无需拆分，直接移动即可。

class Solution {
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        moveDisks(A, B, C, A.size());
    }

    private void moveDisks(List<Integer> start, List<Integer> temp, List<Integer> target, int size) {
        if (size == 1) {
            target.add(start.remove(start.size() - 1));
            return;
        }
        // 借助 c 将 n-1 个盘子放到 b
        moveDisks(start, target, temp, size - 1);
        // a 剩下的一个盘子 放到 c
        target.add(start.remove(start.size() - 1));
        // b 借助 a 将 n-1 个盘子放到 c
        moveDisks(temp, start, target, size - 1);
    }
}

2. 合并两个有序链表

合并有序链表同样适合递归处理。思路很简单：比较两个链表当前头节点的值，选择较小的作为新链表的头，然后让它的 next 指针指向剩余部分的递归结果。递归出口很明确：当其中一个链表为空时，直接返回另一个非空链表。

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        
         (list1.val <= list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
             list1;
        }  {
            list2.next = mergeTwoLists(list2.next, list1);
             list2;
        }
    }
}