递归

递归行为本质上就是基于系统栈的，所有的递归都可以改为迭代。有如下代码，寻找数组 arr[L, R]范围内的最大值，使用递归完成：

public static int process(int[] arr, int L, int R) {
  if (L == R) {
    return arr[L];
  }
  int mid = L + ((R - L) >> 1); // 中点
  int leftMax = process(arr, L, mid);
  int rightMax = process(arr, mid+1, R);
  return Math.max(lefMax, rightMax);
}

每执行一次就压入系统栈，每次执行结束出栈，如此循环。

image-20220109161126709

master公式

Master公式是用来解决递归问题时间复杂度的公式。记录主方法的表现形式：

T(n) = aT(n/b) + O(N^d)

注意，这个公式的前提是子问题的规模是相同的，也就是每个子问题处理的问题规模是相同的。

上述排序arr的代码符合master公式，他的时间复杂度公式为：

T(n) 是关于问题规模 n 的时间复杂度
a 代表父问题与子问题时间复杂度的关系，上述代码递归调用了两次，所以 a = 2
b 代表子问题的规模，上述代码将问题平局拆分为两份分别处理，所以  b = 2
O(N^d) 代表除上述递归的调用，其他代码的总的复杂度，因为上面的代码都是常数时间操作，故 O(N^d)=O(1)，故 d=0

T(n) = 2T(n/2) + O(1)

如果递归满足Master公式，那么时间复杂度为：

1. 如果logbA > d，那么时间复杂度为 O(N^(logbA))

2. 如果logbA < d，那么时间复杂度为 O(N^d)

3. 如果logbA==d，那么时间复杂度为O(N^d * logN)

这里 a = 2， b = 2 ，d = 0，其 logbA = 1 ，所以 logbA > d，故上述代码的时间复杂度为 O(N^(logbA))，即O(N)