为什么在递归函数中使用辅助函数？

Question

在Scala中的函数式编程一书中，在解释如何在函数式编程而不是命令式迭代中经常使用递归的上下文中，作者使用称为“go”或“循环”的辅助函数通过阶乘函数展示了递归，并指出这标准做法是函数式Scala编程：

...
def factorial(n: Int): Int = {
  @tailrec def go(n: Int, acc: Int): Int = {
    if (n <= 0 ) acc
    else go(n - 1, n*acc)
  }
  go(n, 1)
}

...但是人们可以很容易地，如果不是更简洁地定义它而没有辅助函数，因此：

...
def factorial(n: Int): Int = {
  if (n <= 0) 1
    else n * factorial(n - 1)
}

我的理解是，通过利用堆栈帧并将返回值“传递”到前一个堆栈帧，可以在递归中实现累积值和避免突变。在这里，作者似乎出于类似目的使用了显式累加器参数。

使用辅助函数来累积这样的值是否有优势，或者他们是否使用此示例通过将状态显式传递给辅助函数来展示递归与命令式迭代的关系？

Answer 1

尾递归是一项重要的优化，它可以使递归函数更快，并在递归太深时避免“堆栈溢出”。

没有尾递归的递归

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

当我想计算时会发生什么factorial(10)？首先，我计算factorial(9)；然后，我将结果乘以 10。这意味着在计算 时factorial(9)，我需要在某处保留一个注释：“记住，当你完成后factorial(9)，你仍然需要乘以 10！”。

然后为了计算factorial(9)，我必须先计算factorial(8)，然后将结果乘以9。所以我写了一个小纸条“当你有结果时记得乘以9 factorial(8)。

这样继续下去；我终于到了factorial(0)，那就是1。到这个时候，我有十个小笔记，上面写着“完成后记得乘以 1 factorial(0)”、“完成后记得乘以 2 factorial(1)”，等等。

这些笔记被称为“堆栈”，因为它们实际上是堆叠在一起的。如果堆栈变得太大，程序会因“堆栈溢出”而崩溃。

尾递归

def factorial(n: Int): Int = {
  @tailrec def go(n: Int, acc: Int): Int = {
    if (n <= 0 ) acc
    else go(n - 1, n*acc)
  }
  go(n, 1)
}

go这个程序中的功能是不同的。为了计算go(10, 1)你需要计算go(9, 10); 但是当你完成计算后go(9, 10)，你不需要做任何其他事情！可以直接返回结果。所以没必要留个小记“递归调用后记得把结果乘以10”。编译器优化了这种行为：它不是将 to 的调用堆叠在 to 的调用go(9, 10)之上go(10, 1)，而是将togo(10, 1)的调用替换为对的调用go(9, 10)。然后它用对 的调用替换对go(9, 10)的调用go(8, 90)。所以在递归过程中堆栈永远不会增加。这称为尾递归 因为递归调用是函数执行中发生的最后一件事（特别是在评估参数时会发生乘以 10）。