作为一名对技术充满热情的学习者，我一直以来都深刻地体会到知识的广度和深度。在这个不断演变的数字时代，我远非专家，而是一位不断追求进步的旅行者。通过这篇博客，我想分享我在某个领域的学习经验，与大家共同探讨、共同成长。请大家以开放的心态阅读，相信你们也会在这段知识之旅中找到启示。
前言
对于学习编程的同学来说，可能最先接触到的就是遍历算法，但是对于新手来说，如何正确理解遍历以及如何在适当的场合使用遍历，让你的代码变得更加简洁高效是个难以解决问题，下面我们就来好好的聊聊我们熟知而不善使用的递归
一、如何理解递归
理解递归的关键是将大问题分解为小问题，并相信这些小问题的解决方法是正确的。在递归算法中，你可以将问题定义为基本情况和递归情况。基本情况是问题可以直接解决的最小情况，而递归情况则是通过调用自身来解决规模较小但相似的问题。通过这种方式，你逐步解决问题，直到达到基本情况。
例如，考虑计算阶乘的问题。递归地，你可以将计算n的阶乘的问题转化为计算(n-1)的阶乘，一直递归下去，直到n等于1时，就是基本情况，阶乘为1。
二、递归的使用及注意事项
在以下情况中我们是建议使用递归的：
1.问题具有自相似的结构： 当问题可以被分解为规模较小、结构相似的子问题时，递归可以更自然地表达解决方法。
2.树状结构问题： 递归在处理树状结构（如树、图）的问题时非常有用，因为树的节点通常具有相似的属性。
3.分治法： 递归常用于分治法，其中问题被分成若干个相互独立的子问题，然后递归地解决这些子问题。
4.动态规划： 在某些动态规划问题中，递归可以用来建立问题的递归关系，但需要谨慎处理重叠子问题以提高效率。
使用递归时需要注意以下几点：
1.基准情况： 确保定义了递归的基准情况，以防止无限递归。基准情况是递归的结束条件，确保它能够最终被满足。
2.递归深度： 避免递归深度过大，以免导致堆栈溢出。在处理大规模问题时，考虑使用迭代或其他优化方法。
3.重叠子问题： 在使用递归解决动态规划问题时，注意避免重复计算相同的子问题，以提高效率。可以使用记忆化技术或迭代的动态规划方法。
4.性能问题： 递归可能导致性能开销，特别是在调用层数较多的情况下。在需要追求效率的情况下，可能需要考虑迭代或其他非递归方法。
5.清晰性和可读性： 递归的代码结构应当清晰易懂，避免过度复杂化。适当的注释和命名有助于提高代码的可读性。
我就不过多介绍，只需要注意就好，初学者了解即可，后面我们会深度学习递归的底层
三、Java中的遍历经典问题
在Java中，递归经常用于解决需要重复执行相似操作的问题。以下是一些常见的用途：
树结构遍历： 遍历树形结构，如二叉树，可以通过递归来实现。每次递归访问一个节点，并在子树上重复这一过程。
class TreeNode { int val; TreeNode left, right; // ... } void traverseTree(TreeNode node) { if (node != null) { // 处理当前节点 // 递归处理左子树 traverseTree(node.left); // 递归处理右子树 traverseTree(node.right); } }
阶乘计算： 如前所述，计算阶乘是递归的经典例子。
int factorial(int n) { if (n == 0 || n == 1) { return 1; // 基本情况 } else { return n * factorial(n - 1); // 递归情况 } }
问题拆解： 一些问题可以通过不断拆解为子问题来解决，例如归并排序等。
在Java中，遍历二叉树通常使用递归或迭代的方式，包括前序遍历、中序遍历和后序遍历。下面分别展示了这三种遍历的递归实现：
1.前序遍历（Preorder Traversal）：
访问当前节点
递归遍历左子树
递归遍历右子树
class TreeNode { int val; TreeNode left, right; // ... } void preorderTraversal(TreeNode node) { if (node != null) { System.out.print(node.val + " "); // 访问当前节点 preorderTraversal(node.left); // 递归遍历左子树 preorderTraversal(node.right); // 递归遍历右子树 } }
2.中序遍历（Inorder Traversal）：
递归遍历左子树
访问当前节点
递归遍历右子树
void inorderTraversal(TreeNode node) { if (node != null) { inorderTraversal(node.left); // 递归遍历左子树 System.out.print(node.val + " "); // 访问当前节点 inorderTraversal(node.right); // 递归遍历右子树 } }
3.后序遍历（Postorder Traversal）：
递归遍历左子树
递归遍历右子树
访问当前节点
void postorderTraversal(TreeNode node) { if (node != null) { postorderTraversal(node.left); // 递归遍历左子树 postorderTraversal(node.right); // 递归遍历右子树 System.out.print(node.val + " "); // 访问当前节点 } }
四、如何在Java中解决汉诺塔问题
汉诺塔问题是一个经典的递归问题，可以通过递归来解决。在汉诺塔问题中，有三根柱子（A、B、C），A柱上有n个不同大小的圆盘，按照从上到下递增的顺序。目标是将所有圆盘从A柱移动到C柱，可以借助B柱作为辅助。
以下是用递归解决汉诺塔问题的Java代码：
class HanoiTower { // 移动圆盘的函数 void moveDisk(int n, char source, char target, char auxiliary) { if (n == 1) { // 当只有一个圆盘时，直接移动到目标柱子 System.out.println("Move disk 1 from " + source + " to " + target); } else { // 将n-1个圆盘从源柱移动到辅助柱 moveDisk(n - 1, source, auxiliary, target); // 移动第n个圆盘到目标柱 System.out.println("Move disk " + n + " from " + source + " to " + target); // 将n-1个圆盘从辅助柱移动到目标柱 moveDisk(n - 1, auxiliary, target, source); } } public static void main(String[] args) { HanoiTower hanoiTower = new HanoiTower(); int numberOfDisks = 3; // 设置圆盘数量 hanoiTower.moveDisk(numberOfDisks, 'A', 'C', 'B'); } }
此代码演示了如何使用递归函数 moveDisk 解决汉诺塔问题。
五、Java遍历经典面试题
找出二叉树中两个节点的最低公共祖先（Lowest Common Ancestor）：
- 问题： 怎样找出二叉树中两个节点的最低公共祖先？
- 解释： 使用递归，从根节点开始遍历，如果当前节点为null或等于其中一个目标节点，则返回该节点。否则，递归查找左右子树。
下面是Java中的详细代码解释和底层逻辑：
class TreeNode { int val; TreeNode left, right; // ... } public class LowestCommonAncestor { public TreeNode findLowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null || root == p || root == q) { return root; // 当前节点为null或是目标节点之一，直接返回当前节点 } // 递归查找左右子树 TreeNode left = findLowestCommonAncestor(root.left, p, q); TreeNode right = findLowestCommonAncestor(root.right, p, q); if (left != null && right != null) { return root; // 左右子树各包含一个目标节点，当前节点即为最低公共祖先 } else if (left != null) { return left; // 左子树包含目标节点，返回左子树的结果 } else { return right; // 右子树包含目标节点，返回右子树的结果 } } public static void main(String[] args) { // 创建二叉树 TreeNode root = new TreeNode(3); root.left = new TreeNode(5); root.right = new TreeNode(1); root.left.left = new TreeNode(6); root.left.right = new TreeNode(2); root.right.left = new TreeNode(0); root.right.right = new TreeNode(8); root.left.right.left = new TreeNode(7); root.left.right.right = new TreeNode(4); LowestCommonAncestor lca = new LowestCommonAncestor(); // 寻找节点5和节点1的最低公共祖先 TreeNode result = lca.findLowestCommonAncestor(root, root.left, root.right); System.out.println("Lowest Common Ancestor: " + result.val); // 预期输出：3 } }
这段代码通过递归方式
查找最低公共祖先。如果当前节点为null或等于其中一个目标节点，则直接返回当前节点。然后，递归查找左右子树，如果左右子树各包含一个目标节点，当前节点即为最低公共祖先。如果只有一个子树包含目标节点，则返回该子树的结果。这个递归过程最终会回溯到找到最低公共祖先。
总结
当然，对于遍历的总结远不止于此，遍历算法最重要的是让同学们有大问题化为小问题的思想，面对大量的代码循环时，能够抓住问题的根本，用一种方法来解决问题。在遍历算法构建的同时，更应该注重效率，想到更好的算法的情况下，大家还是尽量使用别的方法，实在解决不了在尝试使用遍历。我们需要关注遍历带来的其他不利的影响，别面出现堆栈溢出。
感谢大家抽出宝贵的时间来阅读博主的博客,新人博主,感谢大家关注点赞,祝大家未来的学习工作生活一帆风顺,加油!!!
