递归算法深度剖析
MrHe··3 min read
递归是一种解决问题的方法，它将问题分解为更小的同类子问题，直到达到可以直接解决的基本情况。在算法设计中，递归往往能给出优雅而简洁的解决方案。
递归的本质
递归的核心在于：1) 找到可重复执行的递归模式；2) 确定可以立即解决的基本情况；3) 确保每次递归都能向基本情况靠拢。
经典题型：二叉树的遍历
二叉树的前序、中序和后序遍历是递归思想的典型应用。
方法一：基础递归解法
最直观的递归实现，按照定义直接写出代码。
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
// 前序遍历：根 -> 左 -> 右
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
preorderHelper(root, result);
return result;
}
private void preorderHelper(TreeNode node, List<Integer> result) {
// 基本情况：空节点
if (node == null) {
return;
}
// 处理当前节点
result.add(node.val);
// 递归处理左子树
preorderHelper(node.left, result);
// 递归处理右子树
preorderHelper(node.right, result);
}
// 中序遍历：左 -> 根 -> 右
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
inorderHelper(root, result);
return result;
}
private void inorderHelper(TreeNode node, List<Integer> result) {
if (node == null) {
return;
}
inorderHelper(node.left, result);
result.add(node.val);
inorderHelper(node.right, result);
}
// 后序遍历：左 -> 右 -> 根
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
postorderHelper(root, result);
return result;
}
private void postorderHelper(TreeNode node, List<Integer> result) {
if (node == null) {
return;
}
postorderHelper(node.left, result);
postorderHelper(node.right, result);
result.add(node.val);
}
这种解法的时间复杂度是 O(n)，每个节点只访问一次。空间复杂度是 O(h)，h 是树的高度，这是因为递归调用栈的深度最多为 h。
方法二：迭代解法（用栈模拟递归）
虽然题目要求是递归，但理解递归到迭代的转换有助于深入理解递归的本质。
// 前序遍历的迭代实现
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
result.add(node.val);
// 先压入右孩子，再压入左孩子，这样左孩子会先出栈
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return result;
}
// 中序遍历的迭代实现
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
// 先遍历到最左边的节点
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
result.add(curr.val);
// 转向右子树
curr = curr.right;
}
return result;
}
// 后序遍历的迭代实现（较复杂）
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Stack<TreeNode> stack = new Stack<>();
Stack<TreeNode> output = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
output.push(node);
if (node.left != null) {
stack.push(node.left);
}
if (node.right != null) {
stack.push(node.right);
}
}
while (!output.isEmpty()) {
result.add(output.pop().val);
}
return result;
}
方法三：Morris遍历（空间优化）
Morris遍历是一种特殊的遍历方法，它利用树中的空指针来实现遍历，空间复杂度可以降到 O(1)。
// 前序Morris遍历
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
TreeNode curr = root;
while (curr != null) {
if (curr.left == null) {
result.add(curr.val);
curr = curr.right;
} else {
TreeNode predecessor = curr.left;
while (predecessor.right != null && predecessor.right != curr) {
predecessor = predecessor.right;
}
if (predecessor.right == null) {
result.add(curr.val);
predecessor.right = curr;
curr = curr.left;
} else {
predecessor.right = null;
curr = curr.right;
}
}
}
return result;
}
// 中序Morris遍历
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
TreeNode curr = root;
while (curr != null) {
if (curr.left == null) {
result.add(curr.val);
curr = curr.right;
} else {
TreeNode predecessor = curr.left;
while (predecessor.right != null && predecessor.right != curr) {
predecessor = predecessor.right;
}
if (predecessor.right == null) {
predecessor.right = curr;
curr = curr.left;
} else {
predecessor.right = null;
result.add(curr.val);
curr = curr.right;
}
}
}
return result;
}
Morris遍历的时间复杂度是 O(n)，但空间复杂度降到了 O(1)，因为我们不再需要额外的栈空间。
递归的应用场景
递归适合解决以下类型的问题：
问题的定义本身就是递归的（如树、图的遍历）
问题可以分解为相同类型的更小问题（如分治算法）
需要进行回溯搜索的问题（如组合、排列）
动态规划中某些问题的递归解法
递归的优化技巧
尾递归优化：某些语言（如Scheme）会自动优化尾递归，使其不占用额外栈空间。
// 非尾递归的阶乘 int factorial(int n) { if (n <= 1) return 1; return n * factorial(n - 1); // 递归调用后还有乘法操作 } // 尾递归的阶乘 int factorialTail(int n, int accumulator) { if (n <= 1) return accumulator; return factorialTail(n - 1, n * accumulator); // 递归调用是最后一步操作 }记忆化搜索：在递归中存储已计算结果，避免重复计算。
// 记忆化斐波那契数列 int fib(int n, int[] memo) { if (n <= 1) return n; if (memo[n] != 0) return memo[n]; memo[n] = fib(n - 1, memo) + fib(n - 2, memo); return memo[n]; }迭代转换：对于深度较大的递归，可以转换为迭代实现，避免栈溢出。
递归是算法设计中的一把利器，它让我们能够以简洁优雅的方式解决复杂问题。但也需要注意，递归可能导致性能问题和栈溢出，因此在实际应用中需要权衡利弊，选择合适的实现方式。