数据结构与算法（五）| 递归行为及其时间复杂度分析

锲而舍之，朽木不折；锲而不舍，金石可镂。 ---荀子《劝学》

1. 从思想上理解递归

递归行为从大问题划分为同等结构的小问题着手，每个小问题都和上一级的大问题是同等结构，同等结构的小问题解决了之后所收集来的信息通过分析能够整合出大问题的返回值。

递归就是 「以大化小」 的解决思路。

2. 程序如何运行递归函数

从一个例子来理解递归。

求数组arr[L..R]中的最大值，怎么用递归方法实现。

1）将[L..R]范围分成左右两半。左：[L..Mid] 右：[Mid+1..R] 2）左部分求最大值，右部分求最大值 3） [L..R]范围上的最大值，是max{左部分最大值，右部分最大值}

注意：左部分求最大值，右部分求最大值 是个递归过程，当范围上只有一个数，就可以不用再递归了。

首先，我们把这个递归函数先写出来，然后分析递归函数在系统中是如何运行的。

public int process(int[] arr, int L, int R) {
    //base case
    if (L == R) {
        return arr[L];
    }
    int mid = (L + R) >> 1;
    //递归
    int leftMax = process(arr, L, mid);
    int rightMax = process(arr, mid + 1, R);
    return Math.max(lmax, rMax);
}

给定数组arr = {3, 7, 6, 8, 2, 4, 7, 9}，

数组及其索引下标

要找到该数组的最大元素，就是要调用函数 「process(arr, 0, 7)」 ，执行步骤：

L = 0, R = 7，此时mid = (0 + 7) / 2 = 3，程序运行到第8行 「int leftMax = process(arr, L, mid);」 处时，程序好像又返回去执行了函数 「process(arr, 0, 3)」 ，那么它在系统中其实是暂时把之前运行的一些列 「中间信息暂存到系统栈」 中，此时栈结构：

L = 0，R = 3，此时mid = (0 + 3) / 2 = 1，程序由运行到 「int lMax = process(arr, L, mid);」 位置，即执行函数 「process(arr, 0, 1)」 ，此时又将这一步的中间结果压入系统栈：

L = 0，R = 1，此时mid = (0 + 1) / 2 = 0，程序执行 「int lMax = process(arr, L, mid);」 即执行函数 「process(arr, 0, 0)」 ，此时 L==R，返回arr[L]，也就是arr[0]=3，此时系统栈情况：

这个时候，弹出系统栈顶，并记住此时的leftMax = 3。

此时的栈：

据此恢复递归函数的执行现场：

process(arr,0,1)
mid=0
leftMax=3
rightMax=process(arr,1,1)

虚线栈帧弹出，此时计算出了 「process(arr, 0, 1)」 即arr数组0 ~ 1上的最大值，第10行计算出了0~1上的最大值为7。

此时还原到上一次的递归函数执行现场：

process(arr,0,3)
mid=1
leftMax=process(arr,0,1)=7
rightMax=process(arr,2,3)

继续上述类似入栈步骤，每次入栈都记录程序执行的行数、中间变量等信息。

「TIP：」 递归函数执行过程中，系统帮我们把运行过程中的一些中间信息放到栈中，如果我们自己做一个栈，改成迭代行为，也是可以实现的。因此，「递归函数都可以改写成非递归函数。」

3. 递归函数调用图解

针对上述递归函数，后续我们可以这么画图模拟调用：

递归过程图

这就是递归调用的逻辑图。把调用的过程画出结构图是必须的，这有利于分析递归。

通过一个简单例题的分析得知，递归底层是利用系统栈来实现的。平时分析递归的时候，建议画出逻辑图来辅助分析递归行为。

4. 计算递归算法时间复杂度-Master公式

计算递归算法的时间复杂度可以用Master公式：

时间复杂度为形如

的递归函数，可以直接通过以下条件来确定时间复杂度：

针对本文一开始提出的求数组最大值问题，来根据Master公式分析一下其时间复杂度。

对于数组arr，假设有N个数据的规模，获取最大值的时间复杂度记为：

根据代码，我们把它分为了左侧部分和右侧部分，其数据量分别为N / 2（即「子递归数据规模同等」），所以，左右两侧递归计算的时间复杂度分别为：

所以有：

该递归函数整体上还有一部分时间是计算 「leftMax」 和 「rightMax」 的最大值的，这部分的时间复杂度为O(1)，所以，该递归函数的时间复杂度就是：

所以代入到时间复杂度公式，有：

所以，得出以下条件

再所以，该递归函数的时间复杂度为：

「TIP：」 使用Master公式计算递归时间复杂度的前提：划分的子递归的规模是一样的，即 「同等规模的子递归」 。

首发公众号 「行百里er」 ，欢迎老铁们关注阅读指正。代码仓库 「GitHub」 https://github.com/xblzer/JavaJourney