> For the complete documentation index, see [llms.txt](https://yangsx95.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://yangsx95.gitbook.io/notes/computer-science/shu-ju-jie-gou-he-suan-fa/di-gui.md).

# 递归

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

```java
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](/files/kFiwubQbQ77uOFu3tK12)

## 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)`