Java递归函数：实现分治、搜索和图遍历的基本算法

Java递归函数是一种基于函数自身调用的算法实现方式。递归函数是解决分治、搜索和图遍历问题的基本算法之一。递归函数可以帮助我们有效的解决一些问题，同时也可以帮助我们提高代码的复用性和可读性。在本文中，我们将分别介绍 Java递归函数在这三个方面的应用。

1.分治算法

分治算法是一种将复杂问题分解成简单问题来解决的算法。它通常包括三个步骤：分解、解决和合并。在这种算法中，我们将原问题拆分成若干个子问题，每个子问题互相独立，并且在解决完所有子问题后，将它们的解合并成原问题的解。

使用递归函数实现分治算法时，我们将在每个子问题上调用自身函数。通常，我们会在递归函数中判断是否达到基本情况并返回结果，否则我们将问题拆分成更小的子问题，直到达到基本情况为止。

例如，通过递归实现快速排序算法：

    private static void quickSort(int [] arr, int start, int end) {
        if (start >= end) { // 针对只有一个元素的子数组进行快排时，直接返回
            return;
        }
        int pivotIndex = partition(arr, start, end);
        quickSort(arr, start, pivotIndex-1);//调用自身函数，将左子数组排序
        quickSort(arr, pivotIndex+1, end);//调用自身函数，将右子数组排序
    }
    private static int partition(int[] arr, int left, int right) {
        int pivot = arr[left], i = left + 1, j = right;
        while (i <= j) {
            if (arr[i] > pivot && arr[j] < pivot) {
                swap(arr, i, j);
            }
            if (arr[i] <= pivot) {
                i++;
            }
            if (arr[j] >= pivot) {
                j--;
            }
        }
        swap(arr, left, j);
        return j;
    }
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

在上面的代码中，我们使用了递归函数实现了快速排序算法。我们将整个数组拆分成两个子数组，并在每个子数组上调用自身函数，直到开始进行排序的子数组中只有一个元素为止。

2.搜索算法

搜索算法是解决一些搜索问题的一种常用算法。搜索算法通常可以分为深度优先搜索（DFS）和广度优先搜索（BFS）两种方法。DFS通常使用递归函数实现，而BFS则通常使用队列实现。

在DFS搜索算法中，我们通常使用递归函数实现搜索操作。当达到基本操作时，我们就返回函数；否则我们就在所有相邻的单元格上递归调用自身函数。

例如，使用递归实现DFS搜索二叉树中的节点：

既然是搜索，那么首先要有存在的基本情况。

    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || root.val == val) { // 若当前节点为空或者当前节点就是 target 节点，则返回当前节点
            return root;
        }
        if (val < root.val) { // 若当前节点的值大于 target 节点的值，则 target 节点位于左子树
            return searchBST(root.left, val);//递归调用自身函数，搜索左子树
        } else { // 若当前节点的值小于等于 target 节点的值，则 target 节点位于右子树
            return searchBST(root.right, val);//递归调用自身函数，搜索右子树
        }
    }

在上面的代码中，我们尝试搜索一棵二叉搜索树中是否存在一个具有特定值的节点。我们使用递归函数实现了搜索操作。在函数调用时，如果当前节点为空或者当前节点就是目标节点，则返回当前节点；否则，根据目标值的大小递归地搜索左子树或右子树，直到找到目标节点或搜索到树的末尾。

3.图遍历算法

图遍历算法是解决图论中的问题的一种主要算法。它包括两种遍历方法：深度优先遍历（DFS）和广度优先遍历（BFS）。在DFS中，使用递归函数实现是非常常见的。例如，在无向图中，我们可以使用递归函数实现DFS遍历操作：

    private static void dfs(int[][] graph, boolean[] visited, int currentNode) {
        visited[currentNode] = true; // 标记当前节点已被访问
        System.out.print(currentNode+" ");
        int[] neighbors = graph[currentNode];
        for (int nextNode : neighbors) { // 遍历当前节点的邻居节点
            if (!visited[nextNode]) { // 若当前邻居节点没有被访问，则递归访问该节点
                dfs(graph, visited, nextNode);//递归调用自身函数，访问下一个节点
            }
        }
    }

在上面的代码中，我们尝试搜索无向图中从一个节点出发的所有节点。我们使用递归函数实现了DFS遍历操作。在函数调用时，首先标记当前节点已被访问，然后遍历当前节点的邻居节点，在访问到未被访问的邻居节点时递归访问该节点。

总之，Java递归函数是广泛应用于分治、搜索和图遍历等算法实现中的一种强大的工具。熟练应用递归函数可提高代码复用性和可读性。但是，在递归接近死循环栈溢出的时候需要小心，了解递归函数的优化方法和使用限制。