如何优化Scala double Call of Recursive Function

Question

我正在尝试让这个递归函数工作：

@tailrec
def rec(n: BigInt): BigInt = {
  if (n == 0) 0
  else if (n == 1) 1
  else (rec(n - 1) + rec(n - 2))
}

Error:(13, 24) could not optimize @tailrec annotated method rec: it contains a recursive call not in tail position else (rec(n - 1) + rec(n - 2))

如何优化它以与 tailrec 一起使用？

Answer 1

您将不得不编写一个尾递归辅助函数：

def rec(n: BigInt): BigInt = {
  @tailrec 
  def helper(n: BigInt, previous: BigInt, next: BigInt): BigInt = {
    if (n == 0) previous
    else if (n == 1) next
    else helper(n - 1, next, (next + previous))
  }
  helper(n,0,1)
}

这样一来，您就可以将序列的上一个值和下一个值传递给函数，从而只允许调用一次函数。

这是一种常见的模式，因为许多递归算法只能通过额外的控制流机制（例如：连续传递）来实现尾递归。阶乘是另一个很好的例子，需要编写一个带有额外参数的辅助函数来使其尾递归。

如何优化Scala double Call of Recursive Function

How to optimize Scala double Call of Recursive Function

scala

recursion

tail-recursion