快速排序算法最佳情况递归深度：为何是log n而非log n+1？

核心原因是不同资料对「递归深度」的定义标准不一样，分两种情况说明：

• 主流资料的「log n」定义
  大部分教材、文档里的递归深度，指的是从初始调用之后，发起的递归调用的最大层数——也就是不算最开始的顶层调用，只统计后续递归产生的调用层级。举个例子：
  当n=8时，最佳情况每次均分数组：

  • 顶层调用处理8个元素（不算入递归深度）
  • 第一次递归处理4个元素（第1层）
  • 第二次递归处理2个元素（第2层）
  • 第三次递归处理1个元素（此时触发基准情况，不再继续递归）
    此时递归深度是3，刚好等于log2(8)。

• 你绘制递归树的「log n+1」计数方式
  你在画递归树时，是把顶层调用的节点也算作一层，统计的是从根节点到叶子节点的总节点数（也就是递归树的高度）。还是n=8的例子：

  • 顶层8元素是第1层
  • 4元素是第2层
  • 2元素是第3层
  • 1元素是第4层
    总层数是4，也就是log2(8)+1。

另外补充一点：如果是说「调用栈大小」，不同场景也有差异——有些指的是同时存在于栈中的调用帧最大数量，这时候会包含初始调用，大小就是log n+1；但有些资料会把调用栈大小等同于递归调用的层数，所以用log n。

本质上就是定义的边界问题，只要明确统计的起点和终点，两种说法都没问题，只是主流资料默认采用「不算初始调用的递归层数」这个标准而已。

内容的提问来源于stack exchange，提问作者Jin