让我用简单的例子来解释递归和迭代的区别：
- 递归（Recursion）：
- 函数调用自身来解决问题
- 像是一个套娃过程，每次都把问题变小一点
- 需要有终止条件（不然会无限调用下去）
举个计算阶乘的例子：
// 递归方式计算 5!
public int factorial(int n) {if (n == 1) { // 终止条件return 1;}return n * factorial(n-1); // 调用自己
}// 执行过程：
factorial(5)
= 5 * factorial(4)
= 5 * (4 * factorial(3))
= 5 * (4 * (3 * factorial(2)))
= 5 * (4 * (3 * (2 * factorial(1))))
= 5 * (4 * (3 * (2 * 1)))
= 120
- 迭代（Iteration）：
- 使用循环结构（for、while）来重复执行
- 像是在平地上一步步走
- 用变量来记录状态
同样的阶乘用迭代写：
// 迭代方式计算 5!
public int factorial(int n) {int result = 1;for(int i = 1; i <= n; i++) {result = result * i;}return result;
}// 执行过程：
result = 1
result = 1 * 1 = 1
result = 1 * 2 = 2
result = 2 * 3 = 6
result = 6 * 4 = 24
result = 24 * 5 = 120
主要区别：
-
思维方式
- 递归：把大问题分解成小问题
- 迭代：步步循环，直到完成
-
内存使用
- 递归：每次调用都会占用新的栈空间
- 迭代：只需要循环变量的空间
-
代码风格
- 递归：代码通常更简洁优雅
- 迭代：代码可能更直观易懂
回到你之前问的二叉树遍历的例子：
// 递归方式
public void preorder(TreeNode root) {if (root == null) return;System.out.print(root.val); // 先访问根节点preorder(root.left); // 递归访问左子树preorder(root.right); // 递归访问右子树
}// 迭代方式
public void preorder(TreeNode root) {Stack<TreeNode> stack = new Stack<>();while (root != null || !stack.isEmpty()) {while (root != null) {System.out.print(root.val);stack.push(root);root = root.left;}root = stack.pop().right;}
}
递归在处理树、图这样的数据结构时特别有用，因为它们本身就是递归定义的。但递归也可能导致栈溢出，所以有时候需要改写成迭代形式。
让我解释一下什么是栈溢出(Stack Overflow)：
栈溢出就像往一个杯子里不停倒水，最后水溢出来了一样。具体来说：
- 什么是栈？
// 每调用一个方法，就会在栈上分配一块内存
void methodA() {methodA(); // 递归调用自己
}
- 栈是一块有限的内存空间
- 每次调用方法都会占用一些栈空间
- 方法执行完后会释放这些空间
- 什么情况会栈溢出？
// 容易导致栈溢出的代码
void infiniteRecursion(int n) {System.out.println(n);infiniteRecursion(n + 1); // 没有终止条件的递归
}
- 递归调用太深（比如上面的代码）
- 方法调用层次太多
- 局部变量占用空间太大
- 一个简单的栈溢出例子：
public static void main(String[] args) {count(1);
}public static void count(int n) {System.out.println(n); // 打印当前数字count(n + 1); // 一直递归，没有停止条件
}
// 运行结果：
// 1
// 2
// 3
// ...
// Exception in thread "main" java.lang.StackOverflowError
- 如何避免栈溢出：
// 好的写法：有终止条件
public static void count(int n) {if (n > 1000) return; // 设置终止条件System.out.println(n);count(n + 1);
}// 或者改用循环
public static void count(int n) {while (n <= 1000) {System.out.println(n);n++;}
}
- 设置合适的递归终止条件
- 考虑使用循环替代递归
- 使用尾递归优化（某些语言支持）
- 控制递归深度
所以在写递归代码时，一定要注意设置合适的终止条件，避免无限递归导致栈溢出。
