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

1. 汉诺塔问题

题解思路：递归

将 n 个盘子从 A 柱移到 C 柱（以 A 为起点、C 为目标、B 为辅助）拆分为三个步骤，其中包含两个结构完全相同的子问题：

1. 子问题一：将上面 n-1 个盘子从 A 柱移到 B 柱（以 A 为起点、B 为目标、C 为辅助）
2. 独立操作：将最底层唯一的最大盘子从 A 柱直接移到 C 柱
3. 子问题二：将 n-1 个盘子从 B 柱移到 C 柱（以 B 为起点、C 为目标、A 为辅助）

两个子问题与原问题的解题逻辑完全一致，仅盘子数量、柱子角色不同，符合递归的拆分要求。

每一层递归只处理固定数量的盘子移动，执行完整的三步流程：

1. 先递归调用自身，完成上层 n-1 个盘子的转移，为最大盘子腾出移动空间
2. 执行唯一的直接移动操作，将当前最底层的最大盘子移到目标柱
3. 再次递归调用自身，将之前转移走的 n-1 个盘子，从辅助柱移到目标柱，叠在最大盘子之上

递归过程自顶向下拆分问题，自底向上逐步完成移动，最终合并为完整解。当盘子数量 n = 1 时，无需再拆分，直接将这一个盘子从起始柱移到目标柱即可。

示例代码：

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

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

2. 合并两个有序链表

题解思路：递归

1. 递归函数：接收两个有序链表的头节点，将它们合并为一个新的有序链表，并返回合并后链表的头节点。
2. 函数体逻辑：比较两个链表当前头节点的值，选择值较小的节点作为合并后链表的头节点，然后将该节点的 next 指针指向「剩余两个链表」递归合并后的结果。
3. 递归出口：当其中一个链表为空时，直接返回另一个非空链表（空链表也会被正确处理）。

示例代码：

class  {
     ListNode  {
         (list1 == )  list2;
         (list2 == )  list1;
         (list1.val <= list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
             list1;
        }  {
            list2.next = mergeTwoLists(list2.next, list1);
             list2;
        }
    }
}