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

行百里er 行百里er

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

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