LeetCode排列硬币递归解法为何触发StackOverflowError？

嘿，这个问题我太熟了！咱们一步步拆解来看：

首先得搞懂递归的底层逻辑：每一次递归调用自身时，JVM都会在调用栈里压入一个新的栈帧——这个栈帧要存当前函数的局部变量、返回地址等信息。而JVM的调用栈容量是有限的（默认大小通常在几百KB到几MB之间，具体看运行环境）。

当你输入的n特别大时，递归的深度会变得夸张。比如假设n是1亿，那完整阶梯行数k大概是44721，这意味着递归要连续调用4万多次，每一次都占栈空间，很快就会把JVM的栈资源耗尽，直接触发StackOverflowError。

核心原因是不同环境的JVM栈大小配置不一样！有些IDE可能默认给JVM设置了更大的栈空间（比如通过-Xss参数，比如-Xss2m把栈大小拉到2MB），这样就能容纳更深的递归调用。而你当前用的环境是默认的较小栈空间，扛不住这么深的递归层级，所以就报错了。

其实这个问题完全没必要用递归，效率低还踩栈溢出的坑，给你两个更稳的解法：

• 迭代法：从第1行开始累加硬币数，直到剩余硬币不够放下一行，记录行数即可，完全不会有栈的问题。
• 数学公式法：利用等差数列求和公式，第k行的总硬币数满足 k*(k+1)/2 ≤n，解这个二次不等式取正根的整数部分就行，一行代码搞定，效率O(1)。

比如用Java实现的数学公式解法：

public int arrangeCoins(int n) {
    // 转long避免2*n溢出32位整数
    return (int)(Math.sqrt(2 * (long)n + 0.25) - 0.5);
}

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