Scala快速幂函数触发java.lang.StackOverflowError原因咨询

嘿，我来帮你拆解下为什么会出现java.lang.StackOverflowError，以及怎么修复它～

首先先把你的代码贴出来方便分析：

def fast_power(x:Double, n:Int):Double = {
  if(n % 2 == 0 && n > 1) fast_power(x, n/2) * fast_power(x, n /2)
  else if(n % 2 == 1 && n > 1) x * fast_power(x, n - 1)
  else if(n == 0) 1
  else 1 / fast_power(x, n)
}

核心问题：重复的递归调用 #

你推测的没错，两次调用fast_power(x, n/2)就是栈溢出的罪魁祸首。

正常的快速幂思路是：计算一次x^(n/2)的结果，然后把它平方，这样递归的总调用次数是O(log n)级别的，递归深度也是log n，栈完全能承受。但你的写法里，每次遇到偶数n>1时，会独立调用两次fast_power(x, n/2)——这意味着每一层递归都会分裂出两个新的递归分支，递归树的规模直接从线性对数变成了指数级。

举个例子，当n=8时：

• 第一次调用fast_power(x,8)会触发2次fast_power(x,4)
• 每个fast_power(x,4)又会触发2次fast_power(x,2)，总共4次
• 每个fast_power(x,2)再触发2次fast_power(x,1)，总共8次
  总调用次数是1+2+4+8=15次，而正常写法只需要4次。当n是更大的数（比如2^20），总调用次数会达到2^21-1，这会瞬间把栈空间占满，直接抛出栈溢出错误。

额外的隐患：负数n的无限递归 #

你的最后一个else分支处理负数n时，写的是1 / fast_power(x, n)——这会导致无限递归！比如当n=-1时，会调用1 / fast_power(x, -1)，而fast_power(x, -1)又会进入这个else分支，循环往复直到栈溢出。

修复后的代码 #

把重复的递归调用改成先计算一次子结果再平方，同时修复负数n的处理逻辑：

def fast_power(x: Double, n: Int): Double = {
  def helper(base: Double, exponent: Long): Double = {
    if (exponent == 0) 1.0
    else if (exponent % 2 == 0) {
      val half = helper(base, exponent / 2)
      half * half
    } else {
      base * helper(base, exponent - 1)
    }
  }

  if (n >= 0) helper(x, n.toLong)
  else 1.0 / helper(x, -n.toLong)
}

这里做了几个关键改进：

• 用一个内部helper函数处理正指数，并且把exponent改成Long类型，避免Int负数取绝对值时溢出（比如Int.MinValue的绝对值超过Int范围）
• 只计算一次子问题half，再平方，把递归复杂度拉回O(log n)
• 直接处理负数n：先转成正指数计算，再取倒数，避免无限递归

这样修改后，不管n是大正数还是负数，都不会出现栈溢出的问题啦～

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