大家好，欢迎来到IT知识分享网。

引言

“递归” 一词是比较专业的计算机术语，在现实生活中，有一个更可爱的词——“套娃”。如果把“递归算法”叫做“套娃算法”，或许可以减少一些恐惧程度。

套娃是有限的，同样，递归也是有限的，这和我们经常在影视作品中看到的“无限嵌套循环”是有很大区别的，递归一定存在某个可以返回的节点或条件，否则就会出现栈溢出错误（StackOverflowError）。

其实“套娃”这个词已经足以概括递归算法的本质，就是函数本身调用自身，直到找到一个可以返回的条件，再层层返回。参考《盗梦空间》《明日边缘》等。

递归算法一定可以改写成非递归的实现方式（迭代）。本篇博客将会展示一个简单的递归算法案例，并介绍评估递归算法时间复杂度的 Master公式。

一、案例：数组中的最大值

正如前面所说，递归算法一定可以改写成迭代方式，那么也就是说，递归也属于迭代，只不过它每次迭代的内容，和上一次都是一致的。

假设一个数组，如何用递归的方式找到其中的最大值？

分析，我们可以使用一个类似二分的思路，将数组层层二分，左侧找一个值，右侧找一个值，二者取一个最大。反复这样的过程。

完整代码：

public class RecursionGetMax {

    public static int getMax(int[] arr, int L, int R) {
        if (arr == null || arr.length == 0)
            throw new IllegalArgumentException("参数异常");
        if (arr.length == 1)
            return arr[0];
        // arr[L..R]范围上只有一个数，直接返回，base case
        if (L == R)
            return arr[L];
        // 2个元素以上
        int mid = L + ((R - L) >> 1);
        // 递归取得区域最大
        int leftMax = getMax(arr, L, mid);
        int rightMax = getMax(arr, mid + 1, R);
        return Math.max(leftMax, rightMax);
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 5, 22, 5, 221, 4, 6, 43, 6, 21, 1, 3, 3, 9};
        int max = getMax(arr, 0, arr.length - 1);
        System.out.println(max);
    }
}

注意，这道题在设计时，我们首先要有二分是思路基础，然后我们思考，要设计这样一个函数，这个函数一定会接收一个需要查找的数组，而仅仅传递数组的话，那么就需要在方法中反复拷贝新数组，显然空间复杂度太高，因此，不妨提供额外的两个指针，方便我们选取数组上的数，这样每次传递指针的值，就可以避免每次传递截取的数组。

其次，基础条件也是关键，base case 是可以直接返回的条件，即当 L == R 时，代表我们已经无法再继续二分，因此可以直接返回，这就是最终的返回节点，如果没有这个条件，那么递归将持续执行下去，直到 StackOverflow 。因此，在设计递归方法的时候，一定要考虑好 base case。

二、递归的底层执行与逻辑分析方式

2.1 递归的底层实现

在系统中，递归的实现是使用一个系统栈来完成的，当方法执行到自身调用时，系统会将“现场”保存到系统栈中，擦除局部变量，再重新跳到函数的开头继续执行。

例如，一个数组 arr = {4, 3, 8, 5, 7}，初始 L = 0，R = 4，leftMax的返回值调用过程：

2.2 逻辑分析方式

对于一个希望使用递归实现的方法，我们并不需要每次都画出类似上图的栈结构来详细分析，只需要画出逻辑递归图即可:

例如，arr = {5, 3, 4, 9}，初始 L = 0， R = 3：

三、递归算法的时间复杂度分析

由于递归算法是建立在一种不确定循环次数的情况下，有点类似 do-while 循环，因此，在分析递归算法复杂度形式的时候，只展开第一层的规模。

例如，上述二分取值的方式，就可以写成这样的时间消耗形式：

T(N) = a * T(N/b) + T(N^d)，其中 a，b，d 都是常数

具体的值就是：T(N) = 2 * T(N/2) + O(1) ，a = 2, b = 2, d = 0。

Master 公式，可以直接确定形如上面时间消耗形式的时间复杂度：

如果 logb a < d，复杂度为：O(N^d)

如果 logb a > d，复杂度为：O(N^(logb a))

如果 logb a == d，复杂度为：O(N^d * logN)

其中，logb a，指的是以b为底 a 的对数。案例中的问题，由于log2 > d ，1 >0 ，因此时间复杂度就是 O(N^log2) = O(N) 。