递归树法是一种通过将递归关系可视化为树形结构，来分析递归算法时间复杂度的方法。树中的每个节点代表单次递归调用中所做的工作，而每一层代表递归的一个阶段。下面是我们使用递归树法求时间复杂度的步骤。
- 根据给定的递归关系画出递归 tree。
- 计算每一层的成本，并计算递归树中的总层数。
- 汇总递归树中所有层的成本。
注意： 如果对所有层的求和变得复杂，我们可以通过考虑一个完全满树和/或无限等比数列（比率通常小于1）来找到一个上界。
让我们通过下面的示例代码来理解上述讨论的步骤。
C++
CODEBLOCK_50a885cc
Java
CODEBLOCK_5c5e5065
Python
CODEBLOCK_185cfaa6
C#
CODEBLOCK_7e773cd2
JavaScript
CODEBLOCK_67197b66
理解此代码的递归逻辑
该函数进行了两次递归调用，每次调用处理的问题规模为 INLINECODE9b5848b4。在这两次递归调用返回之后，它执行一个循环，打印 INLINECODEc36296b7 次 "GFG"，这对于每次函数调用来说都是线性工作量。当 n ≤ 1 时，递归停止。
列出递归关系式
每次函数调用都会产生两次规模为 n/2 的递归调用，并在递归后执行线性工作。
因此，递归关系为：T(n) = 2T(n/2) + O(n)
为了求得 T(n)，我们分析递归树并将每一层的成本相加。
> 第 0 层： 根节点贡献的成本为 cn。
>
> 第 1 层： 子问题的规模分别为 n/2 和 n/2。
> 它们的总成本为：c(n/2)+ c(n/2) = cn
>
> 第 2 层： 有四个规模为 n/4 的子问题。
> 以此类推，每一层的工作量保持为 cn。
#### 所有层的总工作量
输入规模在每一层减半，当规模变为常数时递归停止。
因此，递归树的高度为 logn。
由于每一层贡献的成本为 cn，总工作量为：
T(n) = cn + cn + ……. + cn (共 log n 层)
T(n) = cn log n
> 最终结果： T(n) = O(n log n)
另一个关于不等子问题的示例
让我们看下面的代码，这是另一个使用递归树法进行分析的递归代码。
C++
CODEBLOCK_a3cfb03e
Java
CODEBLOCK_eba755d8
Python
CODEBLOCK_f99468c0
C#
CODEBLOCK_b98fcb2b
JavaScript
CODEBLOCK_b972f6c2
理解此代码的递归逻辑
- 该函数进行了两次递归调用：
- 一次的输入规模为
n/4 - 另一次的输入规模为
n/2 - 在递归调用返回后，该函数执行二次 工作，为每一对
(i, j)打印 "GFG"。 - 当
n ≤ 1时，递归停止。
列出递归关系式
递归调用贡献了 T(n/4) 和