Java递归方法案例如何编写

本文目录导读：

1. 基础递归示例：阶乘计算
2. 斐波那契数列
3. 二叉树遍历
4. 汉诺塔问题
5. 数组查找和排序
6. 编写递归的关键要点
7. 递归的优缺点

我来为你介绍Java递归方法的编写案例，从基础到进阶,包含详细解释。

基础递归示例：阶乘计算

public class FactorialExample {
    // 计算n的阶乘
    public static int factorial(int n) {
        // 基准情况：0! = 1
        if (n == 0 || n == 1) {
            return 1;
        }
        // 递归情况：n! = n * (n-1)!
        return n * factorial(n - 1);
    }
    // 带详细打印的版本，帮助理解递归过程
    public static int factorialWithTrace(int n, int depth) {
        // 打印递归深度
        String indent = "  ".repeat(depth);
        System.out.println(indent + "factorial(" + n + ") 调用");
        if (n == 0 || n == 1) {
            System.out.println(indent + "返回 1");
            return 1;
        }
        int result = n * factorialWithTrace(n - 1, depth + 1);
        System.out.println(indent + factorial(n - 1) + " * " + n + " = " + result);
        return result;
    }
    public static void main(String[] args) {
        System.out.println("5! = " + factorial(5));
        System.out.println("\n递归过程追踪：");
        factorialWithTrace(5, 0);
    }
}

斐波那契数列

public class FibonacciExample {
    // 基础递归版本（效率较低）
    public static int fibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
    // 优化版本：使用记忆化递归（动态规划）
    private static int[] memo;
    public static int fibonacciOptimized(int n) {
        memo = new int[n + 1];
        return fibHelper(n);
    }
    private static int fibHelper(int n) {
        if (n <= 1) {
            return n;
        }
        // 如果已经计算过，直接返回
        if (memo[n] != 0) {
            return memo[n];
        }
        // 计算并存储结果
        memo[n] = fibHelper(n - 1) + fibHelper(n - 2);
        return memo[n];
    }
    public static void main(String[] args) {
        int n = 10;
        System.out.println("斐波那契数列第" + n + "项：");
        System.out.println("基础版本: " + fibonacci(n));
        System.out.println("优化版本: " + fibonacciOptimized(n));
    }
}

二叉树遍历

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        this.val = val;
    }
}
public class BinaryTreeTraversal {
    // 前序遍历：根 -> 左 -> 右
    public static void preorder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preorder(root.left);
        preorder(root.right);
    }
    // 中序遍历：左 -> 根 -> 右
    public static void inorder(TreeNode root) {
        if (root == null) {
            return;
        }
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }
    // 后序遍历：左 -> 右 -> 根
    public static void postorder(TreeNode root) {
        if (root == null) {
            return;
        }
        postorder(root.left);
        postorder(root.right);
        System.out.print(root.val + " ");
    }
    // 计算树的高度
    public static int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(height(root.left), height(root.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);
        root.left.right = new TreeNode(5);
        System.out.println("前序遍历：");
        preorder(root);
        System.out.println("\n中序遍历：");
        inorder(root);
        System.out.println("\n后序遍历：");
        postorder(root);
        System.out.println("\n树的高度：" + height(root));
    }
}

汉诺塔问题

public class HanoiTower {
    // 移动步骤计数
    private static int stepCount = 0;
    public static void hanoi(int n, char from, char to, char aux) {
        // 基准情况：只有一个盘子
        if (n == 1) {
            stepCount++;
            System.out.println("步骤" + stepCount + ": 移动盘子1从" + from + "到" + to);
            return;
        }
        // 将n-1个盘子从from移动到aux
        hanoi(n - 1, from, aux, to);
        // 移动最大的盘子
        stepCount++;
        System.out.println("步骤" + stepCount + ": 移动盘子" + n + "从" + from + "到" + to);
        // 将n-1个盘子从aux移动到to
        hanoi(n - 1, aux, to, from);
    }
    // 只计算最少步数
    public static int calculateMinSteps(int n) {
        return (int) Math.pow(2, n) - 1;
    }
    public static void main(String[] args) {
        int n = 3;
        System.out.println("汉诺塔问题（" + n + "个盘子）：");
        hanoi(n, 'A', 'C', 'B');
        System.out.println("\n总步数：" + stepCount);
        System.out.println("理论最少步数：" + calculateMinSteps(n));
    }
}

数组查找和排序

public class RecursiveSearchSort {
    // 二分查找（递归版本）
    public static int binarySearch(int[] arr, int left, int right, int target) {
        if (left > right) {
            return -1;  // 未找到
        }
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            return binarySearch(arr, left, mid - 1, target);
        } else {
            return binarySearch(arr, mid + 1, right, target);
        }
    }
    // 归并排序（递归版本）
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            // 递归排序左右两半
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            // 合并已排序的两半
            merge(arr, left, mid, right);
        }
    }
    private static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        int[] leftArr = new int[n1];
        int[] rightArr = new int[n2];
        // 复制数据到临时数组
        for (int i = 0; i < n1; i++) {
            leftArr[i] = arr[left + i];
        }
        for (int j = 0; j < n2; j++) {
            rightArr[j] = arr[mid + 1 + j];
        }
        // 合并临时数组
        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k] = leftArr[i];
                i++;
            } else {
                arr[k] = rightArr[j];
                j++;
            }
            k++;
        }
        // 复制剩余元素
        while (i < n1) {
            arr[k] = leftArr[i];
            i++;
            k++;
        }
        while (j < n2) {
            arr[k] = rightArr[j];
            j++;
            k++;
        }
    }
    public static void main(String[] args) {
        // 二分查找测试
        int[] sortedArr = {1, 3, 5, 7, 9, 11, 13};
        int target = 7;
        int index = binarySearch(sortedArr, 0, sortedArr.length - 1, target);
        System.out.println("查找" + target + "的位置：" + (index != -1 ? index : "未找到"));
        // 归并排序测试
        int[] unsortedArr = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("\n排序前：");
        for (int num : unsortedArr) {
            System.out.print(num + " ");
        }
        mergeSort(unsortedArr, 0, unsortedArr.length - 1);
        System.out.println("\n排序后：");
        for (int num : unsortedArr) {
            System.out.print(num + " ");
        }
    }
}

编写递归的关键要点

public class RecursionGuidelines {
    /**
     * 编写递归方法的核心原则：
     * 
     * 1. 基准情况（Base Case）：必须有终止条件
     * 2. 递归情况（Recursive Case）：必须向基准情况靠近
     * 3. 问题分解：将大问题分解为相似的小问题
     * 4. 子问题独立：各子问题之间不应该相互依赖
     */
    // 示例：计算数组元素之和
    public static int sumArray(int[] arr, int index) {
        // 基准情况
        if (index >= arr.length) {
            return 0;
        }
        // 递归情况
        return arr[index] + sumArray(arr, index + 1);
    }
    // 尾递归优化的例子
    public static int sumArrayTail(int[] arr, int index, int accumulator) {
        if (index >= arr.length) {
            return accumulator;
        }
        return sumArrayTail(arr, index + 1, accumulator + arr[index]);
    }
    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 5};
        System.out.println("数组求和：" + sumArray(numbers, 0));
        System.out.println("尾递归求和：" + sumArrayTail(numbers, 0, 0));
    }
}

递归的优缺点

优点：

• 代码简洁、逻辑清晰
• 某些问题（如树、图的遍历）天然适合递归
• 解决问题的思路符合直觉

缺点：

• 可能造成栈溢出（StackOverflowError）
• 效率可能比迭代低（函数调用开销）
• 难以调试和优化

适用场景：

• 树、图的数据结构操作
• 分治算法（快速排序、归并排序）
• 回溯算法
• 数学计算（阶乘、斐波那契）

通过以上案例，你可以看到递归方法在不同的场景下的应用，建议先从简单的例子开始实践,慢慢掌握递归的思想。