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

Question

在书 Scala 中的函数式编程 中，在解释递归如何在函数式编程中经常使用命令式迭代的上下文中，作者通过使用阶乘函数的递归展示了递归称为“go”或“loop”的辅助函数，并声明这是函数式 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)
}

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

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

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。这时候我有十个小笔记，上面写着“当你完成 factorial(0) 时记得乘以 1”，“当你完成 factorial(1) 时记得乘以 2”，等等。

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

尾递归

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) 后，你不需要做任何其他事情！您可以直接 return 结果。所以没必要留个小注意“递归调用后记得把结果乘以10”。编译器优化了这种行为：不是将对 go(9, 10) 的调用叠加在对 go(10, 1) 的调用之上，而是将对 go(10, 1) 的调用替换为对 go(9, 10) 的调用。然后它将调用 go(9, 10) 替换为调用 go(8, 90)。因此堆栈在递归期间永远不会增加。这称为 尾递归 因为递归调用是函数执行过程中发生的最后一件事（特别是，乘以 10 发生在评估参数时）。

Answer 2

因为tailrec（尾递归优化）。

如果没有它，在某些时候会出现堆栈溢出（这个问题在这个网站上多么讽刺）异常，而且效率要低得多（主要是内存）。

重要的是要注意 @tailrec 注释不会执行或应用 tailrec 优化，而只是强制编译器在无法优化时失败。

尾递归优化要求您的下一次迭代函数调用应该完全是返回表达式（其中没有额外的操作或计算）。

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

Why use a helper function inside a recursive function?

recursion

functional-programming

scala

tail-recursion

没有尾递归的递归

尾递归