Scala 中的尾递归阶乘函数

Question

我认为下面的阶乘函数是尾递归的，当我测试它时，它可以正常工作到 10 并且在 20 时变得奇怪（负输出），当我插入 100 时，答案是 0：

def factorial(n: Int, m: Int = 1): Int = 
    if (n == 0) m else fact(n-1, m * n)

但是当我把@tailrec放在它上面时，我收到以下错误：

error: not found: type tailrec

我不明白为什么这个函数不是尾递归的。堆栈递归阶乘函数是：

def factorial(n: Int): Int = 
    if (n == 0) 1 else n * factorial(n-1)

上面的函数在每次递归调用时修改else 之后的外部表达式。而第一个函数只修改函数内部的内容。现在，要创建递归阶乘函数，他们所做的是在函数内部创建一个函数。但是，是否可以仅使用此问题中的第一个函数的主体来创建递归阶乘函数？

另外，前一个函数中的“m”是变量吗？

编辑：现在按照答案中的建议进行操作后，如果函数不是尾递归的，我会收到错误消息：

error: could not optimize @tailrec annotated method factorial: it contains a recursive call not in tail position

Answer 1

几件事：

• 您必须导入@tailrec注释才能在没有全名的情况下使用它：

  import scala.annotation.tailrec
  
  @tailrec
  def factorial(n: Int, m: Int = 1): Int = 
    if (n == 0) m else fact(n-1, m * n)
  

  没有@tailrec scalac仍然能够进行尾递归优化，它只是不会强制执行它（如果 TRO 不可能，它不会编译失败）。

• 整数的容量有限 - 它是 32 位2-compliment，并且所有大于 2^31-1 的内容都会溢出并变为负数

因此，您必须导入注释或使用全名 ( @scala.annotation.tailrec) 并替换Int为更大的名称（这Long还不够，更像是BigInteger）。