Scala:尾递归幂函数

avwztpqn  于 2022-11-23  发布在  Scala
关注(0)|答案(3)|浏览(189)

英译汉我总是得到“1”作为结果
这个功能有什么问题?

def power(base: Int, exp: Int): BigInt = {
        def _power(result: BigInt, exp: Int): BigInt = exp match {
            case 0 => 1
            case _ => _power(result*base, exp-1)
        }
        _power(1, exp)
    }
mec1mxoz

mec1mxoz1#

必须替换为:case 0 => result

iq3niunx

iq3niunx2#

可能与OP不相关,但我用这个答案作为例子,这个版本是有效的:

def power(base: Int, exp: Int): BigInt = {
    def _power(result: BigInt, exp: Int): BigInt = exp match {
        case 0 => 1
        case 1 => result
        case _ => _power(result*base, exp-1)
    }
    _power(base, exp)
}
z2acfund

z2acfund3#

更好的尾递归解决方案(堆栈安全)可能如下所示:

def power(base: Int, exp: Int): BigInt {

  @scala.annotation.tailrec
  def loop(x: BigInt, n: Long, kx: BigInt): BigInt = {
    if (n == 1) x * kx
    else {
      if (n % 2 == 0)
        loop(x * x, n / 2, kx)
      else
        loop(x, n - 1, x * kx) // O(log N) time complexity!
    }
  }

  if (n == 0) 1
  else {
    val pow = loop(base, Math.abs(exp.toLong), 1)
    if (n > 0) pow else 1 / pow
  }

}

相关问题