掌握Java递归与数据结构（从零开始学递归算法与Java实现）

简单递归示例：计算阶乘

阶乘是学习递归最经典的入门例子。n 的阶乘（n!）定义为 n × (n-1) × ... × 1，而 0! = 1。

public class Factorial {    public static int factorial(int n) {        // 基础情况：当 n 为 0 或 1 时，返回 1        if (n == 0 || n == 1) {            return 1;        }                // 递归情况：n! = n × (n-1)!        return n * factorial(n - 1);    }    public static void main(String[] args) {        System.out.println(factorial(5)); // 输出：120    }}

递归数据结构：以二叉树为例

许多数据结构天然具有递归性质。例如，二叉树的每个节点包含左右子树，而子树本身也是二叉树。这种结构非常适合用递归来处理。

下面是一个简单的二叉树节点类和一个递归遍历方法（前序遍历）：

class TreeNode {    int val;    TreeNode left;    TreeNode right;    TreeNode(int val) {        this.val = val;    }}public class BinaryTreeTraversal {    public static void preorder(TreeNode node) {        // 基础情况：节点为空则返回        if (node == null) {            return;        }                // 打印当前节点值        System.out.print(node.val + " ");                // 递归遍历左子树        preorder(node.left);                // 递归遍历右子树        preorder(node.right);    }    public static void main(String[] args) {        TreeNode root = new TreeNode(1);        root.left = new TreeNode(2);        root.right = new TreeNode(3);        root.left.left = new TreeNode(4);        preorder(root); // 输出：1 2 4 3    }}

递归 vs 迭代：如何选择？

虽然递归代码简洁易懂，但每次函数调用都会占用栈空间，可能导致栈溢出（Stack Overflow），尤其在处理深度很大的数据结构时。此时可考虑使用迭代（循环）方式替代。

不过，在处理递归数据结构（如树、图、嵌套列表）时，递归往往是最自然、最直观的解法。掌握好Java递归技巧，是成为优秀程序员的重要一步。

小结

通过本篇Java教程，你已经学会了：

• 递归的基本原理和两个必要条件
• 如何用递归实现阶乘计算
• 如何用递归遍历二叉树这类递归数据结构
• 递归的优缺点及适用场景

希望你能动手实践这些例子，加深对递归算法的理解。编程之路，贵在多练！