递归

通俗地讲，递归就是自己调用自己。递归函数的意义，是将一个大问题，分解为若干个同等算法，但规模更小的子问题。通过解决一系列小范围的子问题，总而在大范围上解决整个问题。

求数组的最大值

举个例子，求一个数组中的最大值。常规的做法是扫描整个数据，用一个变量记录下最大值，时间复杂度为 O(N)。

而递归的思想是，要求一个数组中的最大值，假设有 10 个数，那么我只要找出左边 5 个数的最大值，和右边 5 个数的最大值，一比较，就可以得到整个数组的最大值。

因此这个问题被分解为了，求两个长度为 5 的数组中的最大值，这样一个规模更小但算法相同的子问题。

接着看这个 5 个数的数组，要想求他的最大值，我们可以再分一半，如果知道了左边两个数的最大值，和右边 3 个数的最大值，就可以求出这个数组的最大值。

继续看左边的 2 个数，分解为 2 个只有 1 个数的数组，此时我们得到这个问题的最小子问题（base case），当数组只有一个元素时，最大值就是他自己。

public class RecursiveGetMax {
    public static int getMax(int[] arr) {
        if (arr == null || arr.length == 0) {
            throw new IllegalArgumentException("Invalid arguments");
        }
        return process(arr, 0, arr.length - 1);
    }

    private static int process(int[] arr, int left, int right) {
         if (left < 0 || right > arr.length - 1 || left > right) {
            throw new IllegalArgumentException("Invalid arguments");
        }
        if (left == right) {
            return arr[left];
        }
        int mid = left + ((right - left) >> 1);
        int leftMax = process(arr, left, mid);
        int rightMax = process(arr, mid + 1, right);
        return Math.max(leftMax, rightMax);
    }
}

时间复杂度

递归算法的时间复杂度可以用 Master 公式求得，当其满足以下形式时：

其中：

• a 为递归调用次数
• b 为子问题的规模
• d 为除了递归调用之外的操作的时间复杂度

则有：

对于上面这个求最大值的例子，子问题的规模为 1/2，递归调用 2 次，除递归以外的操作时间复杂度为 O(1)。

此时

因此，递归求数组最大元素的操作，时间复杂度也是 O(N)。