为何前两段Java递归代码遇大n（如10^4）会栈溢出，第三段却不会？

栈溢出的本质是递归调用创建的栈帧数量超过了JVM的栈内存容量。Java的HotSpot虚拟机默认不会对所有递归做优化，但在JIT编译阶段，会对满足条件的尾递归进行尾调用消除——也就是复用当前栈帧，而非创建新栈帧，从而避免栈溢出。

三段代码的核心差异 #

前两段代码无法触发尾调用消除，第三段可以，具体原因如下：

1. 尾调用的纯粹性：
   第三段的递归调用是方法的最后一个操作：return print(list, str, n - 1);，执行完递归调用后直接返回结果，无任何额外逻辑，这种纯尾调用结构更容易被JIT识别并优化。
   前两段中，第一段是无返回值的void方法，JIT对这类方法的尾递归优化优先级更低；第二段虽有返回值，但count--是单独语句，相比第三段直接在参数中计算n-1，JIT更难判定为纯尾调用。

2. 参数类型的影响：
   第三段的递归方法参数使用接口类型List<String>，前两段使用具体实现类ArrayList<String>。JIT对接口类型的参数处理更简单，更容易完成尾调用消除优化。

3. 栈帧大小的隐性差异：
   前两段在递归方法内部执行list.add("Coding Ninjas" + " ");，虽编译时字符串拼接会被优化为常量，但相比第三段提前创建字符串并作为参数传递，前两段的栈帧可能包含更多临时变量信息，间接增大栈帧体积，更快触发栈溢出。

关于时间复杂度 #

三段代码的时间复杂度都是O(n)，均需执行n次list.add操作。第三段通过JIT的尾调用消除，同时实现了O(1)的栈空间复杂度，而前两段未被优化时栈空间复杂度为O(n)，因此n较大时会出现栈溢出。

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