递归遍历打印链表的时间复杂度为何不是O(2n)？

针对以下逆序打印单链表的C++递归代码，常见两个疑问：递归实现的耗时是不是一定是循环实现的两倍？这段代码的实际时间复杂度是多少？

void Display(Node* p) {
   if (p != nullptr) {
       Display(p->next);
       std::cout << p->data;
   }
}

这段代码的时间复杂度是O(n)，其中n是链表的节点总数，不存在“递归耗时必然是循环两倍”的固定规律。

把代码的完整执行过程拆成两部分统计操作数就能得出清晰结果：

• 递归调用阶段：从传入的头节点开始，每进一层函数先做判空检查，非空就立刻把下一个节点的地址传进去发起新的递归，直到碰到链表尾部的空指针才停止向下调用。这一段总共会触发n次对应真实节点的函数调用，加1次空指针的终止判断，操作数和n呈线性关系。
• 递归返回阶段：碰到空指针之后就开始逐层往回退，每退回到上一层的函数栈，就执行1次打印当前节点数据的操作，总共要打印n个节点的数据，这部分的操作数同样和n呈线性关系。

两部分操作加起来，总执行次数是常数 * n + 固定额外开销，按照大O复杂度的计算规则，我们只关心操作数随数据规模增长的量级，常数系数、固定开销都会被忽略，因此最终复杂度就是O(n)，不存在因为返回时要执行打印就抬升复杂度等级的情况。

很多人觉得递归调用走了n次，返回打印又走了n次，加起来2n次操作就比循环慢一倍，这个说法根本站不住脚：

• 首先对比的基准就错了。这段递归实现的是从尾到头逆序打印，拿它和从头到尾顺着遍历的正向循环比耗时完全没有意义，二者实现的功能都不一样。如果要写功能完全一致的循环版逆序打印，要么先遍历一遍把所有节点值压到手动维护的栈里，再逐个弹栈打印，总操作数也是2n级别，和递归的操作量级没有差别；如果靠反转链表实现，遍历反转+打印+再反转恢复结构，总操作数比递归还多。
• 其次常数倍的操作差不代表固定两倍耗时，也不改变复杂度等级。就算不考虑功能差异，递归比普通正向循环多出来的只是函数栈帧创建、销毁的开销，这部分开销和打印操作的IO开销比起来占比非常低，实际运行中根本到不了两倍的差距；再加上不同编译器的优化级别不同，栈帧开销的波动很大，从来没有“递归实现就一定比循环慢两倍”的定论。

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