scala - 重构修复尾部递归调用不在尾部位置的方法

Question

考虑以下递归幂法乘法:

import scala.annotation.tailrec
@tailrec def mult(x: Double, n:Int) : Double = {
      n match {
    case 0 => 1
    case 1 => x
    case _ if ((n & 0x01) != 0) =>  x * mult(x*x, (n-1)/2)
    case _ =>  mult(x*x, n/2)
    }
}

编译错误是:

<console>:28: error: could not optimize @tailrec annotated method mult: 
it contains a recursive call not in tail position
             y *  mult(x*x,(n-2)/2)
               ^

所以..鉴于递归调用 是 最后一个条目 - 我认为产品 y *(尾递归子句)有问题？如何正确构建它？

更新

这是已接受答案的修改版本 - 其中我很懒惰，只是在被调用的方法中放置了第三个累加器。

@tailrec def mult(x: Double, n:Int, accum: Double = 1.0) : Double = {
        n match {
      case 0 => accum
      case 1 => accum * x
      case _ if ((n & 0x01) != 0) =>  mult(x*x, (n-1)/2, x * accum)
      case _ =>  mult(x*x, n/2, accum)
      }
  }

mult: (x: Double, n: Int, accum: Double)Double

试试看:

scala> mult(2, 7)
res0: Double = 128.0

scala> mult(2, 8)
res1: Double = 256.0

Answer 1

有两种方法可以解决此类问题。第一个是在调用中移动乘法，可能是通过添加一个辅助方法:

import scala.annotation.tailrec

def mult(x: Double, n: Int): Double = {
  @tailrec
  def go(x: Double, n: Int, mult: Double): Double = n match {
    case 0 => mult
    case 1 => mult * x
    case _ if (n & 0x01) != 0 => go(x * x, (n - 1) / 2, x * mult)
    case _ => go(x * x, n / 2, mult)
  }
  go(x, n, 1)
}

另一个实际上并不是您问题的答案，但在某些情况下它可能是一种更方便的方法。它被称为“蹦床”:

import scala.util.control.TailCalls._

def mult(x: Double, n: Int): Double = {
  def go(x: Double, n: Int): TailRec[Double] = n match {
    case 0 => done(1)
    case 1 => done(x)
    case _ if (n & 0x01) != 0 => tailcall(go(x * x, (n - 1) / 2).map(_ * x))
    case _ => tailcall(go(x * x, n / 2))
  }
  go(x, n).result
}

这不需要您重构您的方法，并且保证不会破坏堆栈，但它确实会引入一些额外的开销。