有些代码比较适合用递推公式来分析，比如归并排序的时间复杂度、快速排序的最好情况时间复杂度；有些比较适合采用递归树来分析，比如快速排序的平均时间复杂度。而有些可能两个都不怎么适合使用，比如二叉树的递归前中后序遍历。
一般递推公式都可以求解递归代码的时间复杂度，但是有些情况，比如快排的平均时间复杂度的分析，用递推公式会涉及非常复杂的数学推导，借助递归树来分析递归算法的时间复杂度就会比较简单。
递归的思想就是，将大问题分解为小问题来求解，然后再将小问题分解为小小问题。这样一层一层地分解，直到问题的数据规模被分解得足够小，不用继续递归分解为止。
如果把这个一层一层的分解过程画成图，它其实就是一棵树，这棵树就叫递归树。
下面是一棵斐波那契数列的递归树，节点里的数字表示数据的规模，一个节点的求解可以分解为左右子节点两个问题的求解。
1570445651316
归并排序每次会将数据规模一分为二，画成递归树，就是下面这个样子：
1570445665505
因为每次分解都是一分为二，所以代价很低，我们把时间上的消耗记作常量 1。每一层归并操作消耗的时间总和是一样的，跟要排序的数据规模有关，我们把每一层归并操作消耗的时间记作 n。
假设这棵树的高度 h，那总的时间复杂度为O(n ∗ h)。
归并排序递归树是一棵满二叉树，满二叉树的高度大约是 log2n，所以，归并排序递归实现的时间复杂度就是 O(nlogn) 。
用递推公式来求解平均时间复杂度：
快速排序在最好情况下，每次分区都能一分为二，这个时候用递推公式 $T(n)=2T(\frac{n}{2})+n$ ,很容易就能推导出时间复杂度是$ O(nlogn)$ 。
假设平均情况下，每次分区之后两个分区的大小比例为 1 : k。当 k = 9时，如果用递推公式的方法来求解时间复杂度的话，递推公式就写成 $T(n)=T(\frac{n}{10})+T(\frac{9n}{10})+n$。
用这个递推公式推导时间复杂度，推导过程非常复杂。现在用递归树来分析这种情况下快速排序的平均情况时间复杂度：