Java 递归应用技巧

递归是一种通过函数调用自身来解决问题的编程技术。在Java中，递归常用于解决分治问题、树形结构遍历或动态规划等场景。以下是递归的核心应用技巧与实例。

递归的基本结构与终止条件

递归函数必须包含终止条件（Base Case），否则会导致无限递归和栈溢出。以下是一个计算阶乘的经典示例：

public class Factorial {
    public static int factorial(int n) {
        if (n == 0 || n == 1) {  // 终止条件
            return 1;
        }
        return n * factorial(n - 1);  // 递归调用
    }

    public static void main(String[] args) {
        System.out.println(factorial(5));  // 输出120
    }
}

递归与分治算法

递归常用于分治算法，如快速排序或归并排序。以下是快速排序的实现：

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivot = partition(arr, low, high);
            quickSort(arr, low, pivot - 1);  // 递归处理左子数组
            quickSort(arr, pivot + 1, high); // 递归处理右子数组
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);
        return i + 1;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));  // 输出[1, 5, 7, 8, 9, 10]
    }
}

递归与树形结构遍历

递归非常适合处理树形结构，例如二叉树的遍历。以下是二叉树的前序遍历实现：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

public class BinaryTree {
    public static void preOrder(TreeNode root) {
        if (root == null) {  // 终止条件
            return;
        }
        System.out.print(root.val + " ");  // 访问根节点
        preOrder(root.left);  // 递归遍历左子树
        preOrder(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);
        preOrder(root);  // 输出1 2 4 5 3
    }
}

递归优化：尾递归与备忘录

递归可能导致重复计算或栈溢出，优化方法包括尾递归和备忘录（Memoization）。以下是斐波那契数列的优化示例：

public class Fibonacci {
    // 普通递归（效率低）
    public static int fib(int n) {
        if (n <= 1) return n;
        return fib(n - 1) + fib(n - 2);
    }

    // 备忘录优化
    public static int fibMemo(int n, int[] memo) {
        if (n <= 1) return n;
        if (memo[n] != 0) return memo[n];
        memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
        return memo[n];
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println(fib(n));  // 输出55
        System.out.println(fibMemo(n, new int[n + 1]));  // 输出55
    }
}

递归与动态规划

递归是动态规划的基础，许多动态规划问题可以通过递归分解子问题解决。以下是爬楼梯问题的递归解法：

public class ClimbingStairs {
    public static int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        return climbStairs(n - 1) + climbStairs(n - 2);
    }

    public static void main(String[] args) {
        System.out.println(climbStairs(5));  // 输出8
    }
}

递归的应用范围广泛，但需注意避免栈溢出和重复计算。合理设计终止条件并结合优化技巧，可以高效解决复杂问题。