个人主页北极的代码欢迎来访作者简介java后端学习者❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺摘要本文系统讲解了递归算法的核心三要素参数与返回值、终止条件和单层递归逻辑。通过调用栈的视角揭示了递归执行时栈帧压栈/弹栈的全过程包括前序、中序、后序遍历的差异本质。文章以二叉树遍历为例详细演示了递归执行时栈帧的变化规律并指出常见错误如栈溢出、空指针异常的产生原因。最后提供了LeetCode二叉树遍历的标准递归实现帮助读者建立递归思维的系统方法论。理解递归的栈机制是掌握复杂递归问题的基础本文为递归学习提供了清晰的框架和实操指导。关于递归我们这里要好好谈一谈递归为什么很多同学看递归算法都是一看就会一写就废。主要是对递归不成体系没有方法论每次写递归算法 都是靠玄学来写代码代码能不能编过都靠运气。本篇将介绍前后中序的递归写法一些同学可能会感觉很简单其实不然我们要通过简单题目把方法论确定下来有了方法论后面才能应付复杂的递归。这里帮助大家确定下来递归算法的三个要素。每次写递归都按照这三要素来写可以保证大家写出正确的递归算法确定递归函数的参数和返回值确定哪些参数是递归的过程中需要处理的那么就在递归函数里加上这个参数 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。确定终止条件写完了递归算法, 运行的时候经常会遇到栈溢出的错误就是没写终止条件或者终止条件写的不对操作系统也是用一个栈的结构来保存每一层递归的信息如果递归没有终止操作系统的内存栈必然就会溢出。确定单层递归的逻辑确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。递归的底层基石调用栈Call Stack1.1 什么是调用栈当程序调用一个函数时CPU 会做三件事压栈把当前函数的“执行现场”保存到栈内存中跳转跳转到被调用函数的代码返回被调用函数执行完后从栈中恢复之前的现场每个“执行现场”称为一个栈帧Stack Frame包含栈帧内容说明返回地址函数执行完后下一步要执行哪条指令参数传入的实参如cur节点局部变量函数内部定义的变量寄存器状态用于恢复现场java // 示例代码 void funcA() { int x 10; funcB(); // ← 调用 funcB 时funcA 的现场被压栈 x 20; } void funcB() { int y 5; // funcB 执行完毕弹出 funcA 的栈帧继续执行 x 20 }栈的内存布局地址从高到低增长实际栈是向下增长text高地址 ┌─────────────┐ │ funcA 栈帧 │ ← 先压入 ├─────────────┤ │ funcB 栈帧 │ ← 后压入当前执行 ├─────────────┤ │ ... │ 低地址 └─────────────┘ 栈顶SP指针指向这里1.2 递归函数调用时的栈帧变化以二叉树前序遍历preorder(root)为例假设树结构text1 / \ 2 3 / 4压栈过程text第1步preorder(1) 被调用 ┌─────────────────┐ │ preorder(1) │ ← 栈顶执行中 │ 参数: cur1 │ │ 返回地址: main │ └─────────────────┘ 第2步preorder(1) 调用 preorder(2) ┌─────────────────┐ │ preorder(2) │ ← 栈顶执行中 │ 参数: cur2 │ │ 返回地址: 1的left调用│ ├─────────────────┤ │ preorder(1) │ │ 参数: cur1 │ └─────────────────┘ 第3步preorder(2) 调用 preorder(4) ┌─────────────────┐ │ preorder(4) │ ← 栈顶执行中 │ 参数: cur4 │ │ 返回地址: 2的left调用│ ├─────────────────┤ │ preorder(2) │ ├─────────────────┤ │ preorder(1) │ └─────────────────┘ 第4步preorder(4) 调用 preorder(null) ┌─────────────────┐ │ preorder(null) │ ← 栈顶执行中 │ 参数: curnull │ │ 返回地址: 4的left│ ├─────────────────┤ │ preorder(4) │ ├─────────────────┤ │ preorder(2) │ ├─────────────────┤ │ preorder(1) │ └─────────────────┘弹栈过程从第4步继续textpreorder(null) 执行发现 cur null直接 return ↓ 弹出 null 的栈帧回到 preorder(4) 的 left 调用之后 preorder(4) 继续执行preorder(4.right) → 又是 null ↓ 再次压栈/弹栈 null preorder(4) 执行完毕 → 弹出回到 preorder(2) preorder(2) 继续执行preorder(2.right) → 调用 preorder(null) ↓ 压栈/弹栈 preorder(2) 执行完毕 → 弹出回到 preorder(1) preorder(1) 继续执行preorder(1.right) → 调用 preorder(3) ↓ ...以此类推递归三要素背后的原理现在我们用栈的视角来解释为什么需要三要素2.1 要素一参数和返回值原理每次压栈时函数的参数和返回值需要保存在栈帧中。java void traversal(TreeNode cur, ListInteger result) // ← 这些会存入栈帧为什么参数必须是需要的每个参数都存在栈帧里过多的参数会增大栈帧大小栈总大小是有限的通常 JVM 默认 512KB ~ 1MB参数越多→栈帧越大→能容纳的递归深度越小这就是为什么深度递归如 10 万层会栈溢出。不是代码错了是栈装不下了。2.2 要素二终止条件Base Case原理没有终止条件 永远不会弹栈 无限压栈直到栈溢出。java if (cur null) return; // ← 这是弹栈的唯一出口栈溢出示例java void badRecursion(int n) { // 没有终止条件 badRecursion(n - 1); // 永远不返回 }对应的栈状态text栈帧1: badRecursion(100) 栈帧2: badRecursion(99) 栈帧3: badRecursion(98) ... 栈帧N: badRecursion(???) ┌─────────────────┐ │ ... │ │ 当栈满了 ───→ │ StackOverflowError └─────────────────┘注意终止条件不一定是cur null根据问题不同可以是n 0node.next nullstart end二分查找左边界 右边界关键是递归要在某个条件下停止继续压栈。2.3 要素三单层递归逻辑原理这是定义“当前栈帧做什么”以及“如何创建下一层栈帧”。java // 前序遍历的单层逻辑 result.add(cur.val); // 当前栈帧的工作 traversal(cur.left, result); // 创建下一层栈帧左 traversal(cur.right, result); // 创建下一层栈帧右栈帧视角text当前栈帧(cur某节点): 1. 处理本节点的数据添加到result 2. 创建左子树的栈帧压栈 3. 等左子树完全弹栈后创建右子树的栈帧压栈 4. 本栈帧结束弹栈为什么顺序很重要前/中/后的本质三种遍历的区别仅仅是“处理当前节点”在递归调用之间出现的位置遍历方式代码顺序处理时机前序处理 → 左递归 → 右递归压栈时立即处理中序左递归 → 处理 → 右递归左子树弹完后处理后序左递归 → 右递归 → 处理左右子树都弹完后处理栈帧中的时序以前序遍历为例text时间 → preorder(1): 处理1 → 调用左 → 等待左返回 → 调用右 → 等待右返回 → 返回 ↓ preorder(2): 处理2 → 调用左 → 等待左返回 → 调用右 → 等待右返回 → 返回 ↓ preorder(4): 处理4 → 调用左(null) → 立即返回 → 调用右(null) → 立即返回 → 返回错误原理后果忘记终止条件没有弹栈出口StackOverflowError终止条件位置错误在访问节点值之后才判断 nullNullPointerException返回值类型混乱栈帧不知道如何处理返回值编译错误或数据错误递归深度过大栈的大小有限StackOverflowError可改尾递归或迭代假设有这样一棵树text1 / \ 2 3 / \ 4 5前序遍历顺序应该是1, 2, 4, 5, 3递归执行过程逐步分解java // 第1步从根节点1开始 traversal(节点1, list) { list.add(1); // 输出 1 traversal(节点1.left, list); // 进入左子树节点2 traversal(节点1.right, list); // 等左子树全部遍历完才会执行这行 } // 第2步进入节点2节点1的左子树 traversal(节点2, list) { list.add(2); // 输出 2 traversal(节点2.left, list); // 进入节点4 traversal(节点2.right, list); // 等节点4遍历完再执行 } // 第3步进入节点4节点2的左子树 traversal(节点4, list) { list.add(4); // 输出 4 traversal(节点4.left, list); // 节点4.left null直接return traversal(节点4.right, list); // 节点4.right null直接return } // 节点4执行完毕返回到节点2的traversal函数 // 第4步回到节点2执行剩下的 traversal(节点2.right, list) traversal(节点5, list) // 节点2的右子树 { list.add(5); // 输出 5 traversal(节点5.left, list); // nullreturn traversal(节点5.right, list); // nullreturn } // 节点5执行完毕返回到节点2 // 节点2执行完毕返回到节点1 // 第5步回到节点1执行 traversal(节点1.right, list) traversal(节点3, list) { list.add(3); // 输出 3 traversal(节点3.left, list); // null traversal(节点3.right, list); // null }最终输出顺序1, 2, 4, 5, 3 ✅关键理解点递归是嵌套的执行traversal(cur.left, list)时会进入一个新函数这个新函数内部又会调用自己的traversal(cur.left, list)后行代码等待只有当traversal(cur.left, list)这整条递归链完全执行完毕即左子树所有节点都处理完才会执行下一行traversal(cur.right, list)栈的机制每个递归调用都会在系统栈中压栈执行完返回时出栈保证了顺序正确实战演练144.二叉树的前序遍历/** * Definition for a binary tree node. * public 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; * } * } */ class Solution { public ListInteger preorderTraversal(TreeNode root) { ListInteger resultnew ArrayList(); preorder(root,result); return result; } public void preorder(TreeNode root,ListIntegerresult){ if(rootnull){ return; } result.add(root.val); preorder(root.left,result); preorder(root.right,result); } }145.二叉树的后序遍历/** * Definition for a binary tree node. * public 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; * } * } */ class Solution { public ListInteger postorderTraversal(TreeNode root) { ListInteger resultnew ArrayList(); lateorder(root,result); return result; } public void lateorder(TreeNode root,ListInteger result){ if(rootnull){ return; } lateorder(root.left,result); lateorder(root.right,result); result.add(root.val); } }94.二叉树的中序遍历/** * Definition for a binary tree node. * public 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; * } * } */ class Solution { public ListInteger inorderTraversal(TreeNode root) { ListInteger res new ArrayList(); inorder(root, res); return res; } void inorder(TreeNode root, ListInteger list) { if (root null) { return; } inorder(root.left, list); list.add(root.val); // 注意这一句 inorder(root.right, list); } }结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励