递归算法及其时间复杂度分析

电玩女神 2022-10-22 07:40 31阅读 0赞

# 引言 #

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

套娃是有限的，同样，递归也是有限的，这和我们经常在影视作品中看到的“无限嵌套循环”是有很大区别的，递归一定存在某个可以返回的节点或条件，否则就会出现栈溢出错误（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的返回值调用过程：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3NDUwNjk_size_16_color_FFFFFF_t_70][]

## 2.2 逻辑分析方式 ##

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

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3NDUwNjk_size_16_color_FFFFFF_t_70 1][]

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

由于递归算法是建立在一种不确定循环次数的情况下，有点类似 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) 。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3NDUwNjk_size_16_color_FFFFFF_t_70]: /images/20221022/6234e34b97e64fde88a195ae4574a520.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3NDUwNjk_size_16_color_FFFFFF_t_70 1]: /images/20221022/2fbc31288eed47f19b942a04e294ba92.png