### Java 实现的经典递归算法三例详解
#### 一、汉诺塔问题
汉诺塔（Tower of Hanoi）是一种经典的递归问题，在计算机科学领域有着广泛的应用。该问题通常表述为：有三个柱子 A、B 和 C，以及 n 个不同大小的圆盘。所有圆盘最初都在柱子 A 上，且按照大小顺序从下到上依次排列。目标是将这些圆盘全部移动到柱子 C 上，并保持同样的顺序。在移动过程中，每次只能移动一个圆盘，并且任何时候都不能将一个较大的圆盘放在较小的圆盘之上。
**代码分析：**
```java
public class Hanoi {
private static final String DISK_A = "diskA";
private static final String DISK_B = "diskB";
private static final String DISK_C = "diskC";
static String from = DISK_A;
static String to = DISK_C;
static String mid = DISK_B;
public static void main(String[] args) {
String input = JOptionPane.showInputDialog("please input the number of the disks you want me move.");
int num = Integer.parseInt(input);
move(num, from, mid, to);
}
private static void move(int num, String from, String mid, String to) {
if (num == 1) {
System.out.println("move disk 1 from " + from + " to " + to);
} else {
move(num - 1, from, to, mid); // 将 n-1 个盘子从 A 柱通过 C 柱移动到 B 柱
System.out.println("move disk " + num + " from " + from + " to " + to);
move(num - 1, mid, from, to); // 将 n-1 个盘子从 B 柱通过 A 柱移动到 C 柱
}
}
}
```
**解析：**
1. **定义柱子**：使用 `String` 类型定义了三个柱子的名称。
2. **初始化变量**：通过 `JOptionPane.showInputDialog` 获取用户输入的盘子数量。
3. **核心递归函数**：
- 当 `num == 1` 时，直接将盘子从 `from` 柱子移动到 `to` 柱子。
- 当 `num > 1` 时，先将 `n-1` 个盘子从 `from` 移动到 `mid`，再将最大的一个盘子从 `from` 移动到 `to`，最后将 `n-1` 个盘子从 `mid` 移动到 `to`。
#### 二、字符串全排列问题
全排列问题是指给定一个字符串，求出该字符串的所有可能的排列组合。例如，对于字符串 "abc"，其所有可能的排列为 "abc"、"acb"、"bac"、"bca"、"cab" 和 "cba"。
**代码分析：**
```java
public class Permutation {
public static void permute(String str) {
char[] strArray = str.toCharArray();
permute(strArray, 0, strArray.length - 1);
}
public static void permute(char[] list, int low, int high) {
int i;
if (low == high) {
String cout = "";
for (i = 0; i <= high; i++) {
cout += list[i];
}
System.out.println(cout);
} else {
for (i = low; i <= high; i++) {
char temp = list[low];
list[low] = list[i];
list[i] = temp;
permute(list, low + 1, high);
temp = list[low];
list[low] = list[i];
list[i] = temp;
}
}
}
}
```
**解析：**
1. **初始化**：将字符串转换为字符数组。
2. **递归过程**：
- 如果当前层次只剩下一个字符，则直接输出。
- 否则，遍历剩余的所有字符，进行交换，并递归调用。
3. **恢复现场**：在返回之前，需要将交换的字符恢复原位。
#### 三、组合问题
组合问题是求从给定的元素集中取出一定数量的元素的所有可能组合。例如，从字符串 "abc" 中取两个字符的所有组合为 "ab"、"ac" 和 "bc"。
**代码分析：**
```java
public class Combination {
public static void main(String[] args) {
String input = JOptionPane.showInputDialog("please input your String");
String numString = JOptionPane.showInputDialog("please input the number of your Combination");
int num = Integer.parseInt(numString);
combine(input, num);
}
private static void combine(String input, int num) {
char[] a = input.toCharArray();
String b = "";
combine(a, num, b, 0, a.length);
}
private static void combine(char[] a, int num, String b, int low, int high) {
if (num == 0) {
System.out.println(b);
} else {
for (int i = low; i < a.length; i++) {
b += a[i];
combine(a, num - 1, b, i + 1, a.length);
b = b.substring(0, b.length() - 1);
}
}
}
}
```
**解析：**
1. **初始化**：获取用户输入的字符串和组合长度。
2. **递归过程**：
- 当 `num == 0` 时，表示已经选取了所需的组合数，直接输出结果。
- 否则，从当前位置开始选择字符，并递归调用。
3. **回溯**：在返回之前，将添加的字符移除，以便于下次循环选择其他字符。
以上三个示例展示了如何使用 Java 实现递归算法解决经典问题。这些算法不仅可以帮助我们更好地理解递归思想，还能在实际编程中发挥重要作用。
