特点
数据结构的一种特殊应用
借助递归树来分析递归算法的时间复杂度
如果把这个一层一层的分解过程画成图，它其实就是一棵树，叫作递归树
如何用递归树来求解时间复杂度?
1.分析归并排序的时间复杂度
每次分解都是一分为二，把时间上的消耗记作常量1。
归并算法中比较耗时的是归并操作，也就是把两个子数组合并为大数组。
从图中可以看出，每一层归并操作消耗的时间总和是一样，跟要排序的数据规模有关。
把每一层归并操作消耗的时间记作n。
现在这棵树的高度h，用高度h乘以每一层的时间消耗n，就可以得到总的时间复杂度O(n*h)
从归并排序的原理和递归树可以看出来，归并排序递归树是一棵满二叉树
满二叉树的高度大约是，所以，归并排序递归实现的时间复杂度就是O(n * log n)
2.分析快速排序的时间复杂度
快速排序过程中，每次分区都要遍历待分区区间的所有数据，操作所遍历数据个数之和是n
现在只要求出递归树的高度h，快排过程遍历的数据个数是h * n，时间复杂度就是O(h * n)
因为每次分区并不是均匀地一分为二，所以递归树并不是满二叉树
根据复杂度的大O表示法，对数复杂度的底数统一写成logn，时间复杂度仍然是O(n*log n)
3.分析斐波那契数列的时间复杂度
如果路径⻓度都为n，那这个总和就是-1
近似推导上面算法的时间复杂度是指数级的，非常高
总结
比较适合用递推公式来分析，比如
归并排序时间复杂度、快速排序的最好情况时间复杂度
比较适合采用递归树来分析，比如
快速排序的平均时间复杂度
有些可能两个都不怎么适合使用，比如
二叉树的递归前中后序遍历
