先理解一下递归如何执行.

首先看下找数组最大值的循环代码.

int maxValue = INT_MIN;
for (int i = 0; i < nums.size(); ++i) {
		maxValue = max(maxValue, nums[i]);
}

递归代码1

int findMax(const vector<int>& nums, int index) {
    if (index == nums.size() - 1) {
        return nums[index];
    }
    int restMax = findMax(nums, index + 1);
    return max(nums[index], restMax);
}
int maxValue = nums.empty() ? INT_MIN : findMax(nums, 0);

假设数组为{3, 1, 4, 2}, 调用过程:

               findMax(0) return 4 ✅
                  |
          ┌───────┴────────┐
          |                |
    nums[0] = 3      findMax(1) ⬆️
                         |
                 ┌──────┴──────┐
                 |             |
           nums[1] = 1    findMax(2) return 4 ⬆️
                              |
                      ┌──────┴──────┐
                      |             |
                nums[2] = 4    findMax(3) return 4 ⬆️
                                    |
                          ┌────────┴────────┐
                          |                 | 
                    nums[3] = 2     ✅ base case → return 2 ⬆️

递归代码2

int findMax(const vector<int>& nums, int left, int right) {
    if (left == right) {
        // 区间只有一个元素
        return nums[left];
    }

    int mid = (left + right) / 2;
    int leftMax = findMax(nums, left, mid);
    int rightMax = findMax(nums, mid + 1, right);
    return max(leftMax, rightMax);
}
int maxValue = nums.empty() ? INT_MIN : findMax(nums, 0, nums.size() - 1);

                             findMax(0, 3)
                             /          \\
                findMax(0, 1)            findMax(2, 3)
                 /       \\                /        \\
        findMax(0,0)   findMax(1,1)  findMax(2,2)  findMax(3,3)
            ↓              ↓             ↓             ↓
        return 3       return 1      return 4       return 2
                 \\        /               \\         /
         ← max(3,1)=3                     ← max(4,2)=4
                      \\                   /
                          ← max(3,4) = 4

Master公式

$T(N) = a*T(N/b)+O(N^c)$

master公式可以解决递归问题划分成等规模的若干子问题的复杂度计算. 也就是将整个大问题, 划分成a个b分之N的小问题. 不能计算不等规模子问题的复杂度, 比如一个子问题三分之一, 另一个子问题三分之二.