递归算法题
- 求阶乘（Factorial）
- 斐波那契数列（Fibonacci Sequence）
- 汉诺塔（Tower of Hanoi）
- 遍历树节点（Tree Traversal）
- 数组反转（Array Reversal）
- 爬楼梯问题（Climbing Stairs Problem）
- 回文数检测（Palindrome Checking）
- 找出数组中的最大值（Finding Maximum Value in an Array）
- 分治算法 - 归并排序（Merge Sort）
- 搜索二叉搜索树（BST）中的元素（Search in a Binary Search Tree）
- 使用递归遍历一个给定的目录下的所有文件
- 用递归实现字符串倒转
- 求解括号匹配问题（Parentheses Matching Problem）
1. 阶乘（Factorial）
计算一个非负整数 n 的阶乘（n!），即 n × (n-1) × … × 2 × 1。
public int factorial(int n) {
if (n == 0 || n == 1) {
// 递归的基本情况
return 1;
} else {
return n * factorial(n - 1); // 递归调用
}
}
2. 斐波那契数列（Fibonacci Sequence）
计算第 n 项斐波那契数（F(n) = F(n-1) + F(n-2)，其中 F(0) = 0, F(1) = 1）。
public long fibonacci(int n) {
if (n <= 1) {
// 递归的基本情况
return n;
} else {
return fibonacci(n - 1) + fibonacci(n - 2); // 递归调用
}
}
3. 汉诺塔（Tower of Hanoi）
解决汉诺塔问题，把所有盘子从柱子 A 移动到柱子 C，每次只能移动一个盘子，且任何时候大盘子都不能压在小盘子上面。
public void moveDisk(char from, char to, char aux, int numDisks) {
if (numDisks == 1) {
// 基础情况
System.out.println("Move disk 1 from " + from + " to " + to);
} else {
moveDisk(from, aux, to, numDisks - 1); // 递归地将 n-1 个盘子从 A 移到 B
System.out.println("Move disk " + numDisks + " from " + from + " to " + to);
moveDisk(aux, to, from, numDisks - 1); // 递归地将 n-1 个盘子从 B 移到 C
}
}
4. 遍历树节点（Tree Traversal）
使用递归来实现二叉树的各种遍历方式，例如前序遍历、中序遍历和后序遍历。
class Node {
int data;
Node left, right;
// 构造函数和其它辅助方法...
}
// 前序遍历
public void preorderTraversal(Node nod