Scala 中的快速幂函数

Question

我试图在 scala 中编写一个函数以实现快速功率，但我一直得到 java.lang.WhosebugError。我认为这与我为 n/2 递归调用此函数时在第三行中使用的两个斜杠有关。谁能解释为什么会这样

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)
}

Answer 1

更喜欢 match 构造而不是多个 if/else 块。这将帮助您隔离问题（错误的递归调用），并编写更易于理解的递归函数。永远把终止条件放在第一位。

def fastPower(x:Double, m:Int):Double = m match {
  case 0 => 1
  case 1 => x
  case n if n%2 == 0 => fastPower(x, n/2) * fastPower(x, n/2)
  case n => x * fastPower(x, n - 1)
}

Answer 2

您的代码不会终止，因为 n = 1 不存在。此外，您的 fast_power 具有线性运行时间。

如果你这样写下来：

def fast_power(x:Double, n:Int):Double = {
  if(n < 0) {
    1 / fast_power(x, -n)
  } else if (n == 0) {
    1.0
  } else if (n == 1) {
    x
  } else if (n % 2 == 0) {
    val s = fast_power(x, n / 2)
    s * s
  } else {
    val s = fast_power(x, n / 2)
    x * s * s
  }
}

那么很明显运行时间是对数的，因为 n 在每次递归调用中至少减半。

我对if-vs-match没什么强烈的意见，所以我就把所有的案例按升序排列了。

Scala 中的快速幂函数

fast power function in scala

recursion

scala

exponentiation