# 递归

递归行为本质上就是基于系统栈的，所有的递归都可以改为迭代。有如下代码，寻找数组 `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)`


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://yangsx95.gitbook.io/notes/computer-science/shu-ju-jie-gou-he-suan-fa/di-gui.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.