尾递归

使用常规递归，每个递归调用将另一个条目推送到调用堆栈。递归完成后，应用程序必须将每个条目一直弹回。如果有很多递归函数调用，它最终会有一个巨大的堆栈。

如果在尾部位置找到递归调用，Scala 会自动删除递归。可以将注释（@tailrec）添加到递归函数以确保执行尾调用优化。如果编译器无法优化你的递归，则会显示错误消息。

定期递归

这个例子不是尾递归的，因为当进行递归调用时，函数需要跟踪调用返回后它需要对结果进行的乘法。

def fact(i : Int) : Int = {
   if(i <= 1) i
   else i * fact(i-1)
}

println(fact(5))

使用参数调用函数将产生如下所示的堆栈：

(fact 5)
(* 5 (fact 4))
(* 5 (* 4 (fact 3)))
(* 5 (* 4 (* 3 (fact 2))))
(* 5 (* 4 (* 3 (* 2 (fact 1)))))
(* 5 (* 4 (* 3 (* 2 (* 1 (fact 0))))))
(* 5 (* 4 (* 3 (* 2 (* 1 * 1)))))
(* 5 (* 4 (* 3 (* 2))))
(* 5 (* 4 (* 6)))
(* 5 (* 24))
120

如果我们尝试使用 @tailrec 注释此示例，我们将收到以下错误消息：could not optimize @tailrec annotated method fact: it contains a recursive call not in tail position

尾递归

在尾递归中，首先执行计算，然后执行递归调用，将当前步骤的结果传递给下一个递归步骤。

def fact_with_tailrec(i : Int) : Long = {
   @tailrec
   def fact_inside(i : Int, sum: Long) : Long = {
      if(i <= 1) sum
      else fact_inside(i-1,sum*i)
   }
   fact_inside(i,1)
}

println(fact_with_tailrec(5))

相反，尾递归阶乘的堆栈跟踪如下所示：

(fact_with_tailrec 5)
(fact_inside 5 1)
(fact_inside 4 5)
(fact_inside 3 20)
(fact_inside 2 60)
(fact_inside 1 120)

每次调用 fact_inside 时，只需要跟踪相同数量的数据，因为该函数只是将它所获得的值返回到顶部。这意味着即使调用 fact_with_tail 1000000，它也只需要与 fact_with_tail 3 相同的空间量。非尾递归调用不是这种情况，因此大值可能导致堆栈溢出。