掌握递归思想与算法设计
递归是一种强大的编程技术，其中函数调用自身来解决更小规模的相同问题。递归在算法设计、数据结构操作和问题求解中发挥着重要作用。
public static long factorial(int n) {
if (n <= 1) {
return 1; // 基础情况
}
return n * factorial(n - 1); // 递归情况
}public static long fibonacci(int n) {
if (n <= 1) {
return n; // 基础情况
}
return fibonacci(n-1) + fibonacci(n-2);
}public static void hanoi(int n, char from,
char aux, char to) {
if (n == 1) {
System.out.println("Move " + from + " to " + to);
return;
}
hanoi(n-1, from, to, aux);
hanoi(1, from, aux, to);
hanoi(n-1, aux, from, to);
}// 递归求和
public static int sum(int n) {
if (n <= 0) return 0;
return n + sum(n - 1);
}// 迭代求和
public static int sum(int n) {
int result = 0;
for (int i = 1; i <= n; i++) {
result += i;
}
return result;
}理解递归算法的时间和空间复杂度对于选择合适的算法实现至关重要：
| 算法 | 时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|
| 阶乘（递归） | O(n) | O(n) | 线性递归，调用栈深度为n |
| 斐波那契（朴素递归） | O(2^n) | O(n) | 指数时间，存在大量重复计算 |
| 斐波那契（记忆化） | O(n) | O(n) | 通过缓存避免重复计算 |
| 二分查找（递归） | O(log n) | O(log n) | 每次递归问题规模减半 |
| 快速排序（递归） | O(n log n) | O(log n) | 分治算法，平均情况 |
| 汉诺塔 | O(2^n) | O(n) | 指数时间，最优解 |
private static Map cache = new HashMap<>();
public static long fibonacciMemoized(int n) {
if (n <= 1) return n;
if (cache.containsKey(n)) {
return cache.get(n);
}
long result = fibonacciMemoized(n-1) + fibonacciMemoized(n-2);
cache.put(n, result);
return result;
} public static long factorialTail(int n) {
return factorialHelper(n, 1);
}
private static long factorialHelper(int n, long acc) {
if (n <= 1) return acc;
return factorialHelper(n - 1, n * acc);
}public static long fibonacciDP(int n) {
if (n <= 1) return n;
long[] dp = new long[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}点击下面的按钮，在在线IDE中查看和运行完整的递归示例代码：