如何优化递归功能的Scala双重调用

Question

我正在尝试使此递归功能工作：

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

错误：（13，24）无法优化@tailrec注释方法rec：它包含一个不在尾部位置的递归调用 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)
}

这是，因此您可以将序列的上一个和下一个值传递给函数，从而使您只能接到一个呼叫。

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