为什么要在递归函数内部使用辅助函数？

Question

为什么要在递归函数内部使用辅助函数？

scalarecursionfunctional-programmingtail-recursion

4

在《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)
}

我理解，在递归中通过利用堆栈帧并向前一级堆栈帧“传递”返回值，可以实现积累值和避免变异。在这里，作者似乎正在使用显式的累加器参数来实现类似的目的。

使用辅助函数来累加值是否有优势，还是他们使用这个示例来展示递归如何与命令式迭代相关联，通过向辅助函数显式传递状态来实现?

- Aaron

4

由于尾递归优化，否则会出现堆栈溢出异常（多么具有讽刺意味，这个问题在这个网站上）。同时，没有尾递归优化的代码执行效率也要低得多。 - Artem Sokolov

@ArtemSokolov 但第二个版本不会导致堆栈溢出，对吧？它会触发基本情况。或者你的意思是没有注释，编译器无法抱怨如果不能进行尾调用优化，而你无法在外部函数上放置注释？ - Aaron

尾递归不使用调用栈，而是使用累加器，因此前者可以被消除。这种累加器风格的递归在底层就是一个循环。在惰性环境中，您可以选择使用惰性右折叠作为替代方案。惰性计算自然而然地提供了免费的堆栈安全性。 - user5536315

2

@Aaron注解不适用于尾递归，它只会强制编译器在未进行优化时失败。第二个版本将因为栈溢出而失败，因为没有尾递归优化，也没有函数的尾递归结构。 - Artem Sokolov

啊，我明白了，在第二种情况下，在递归调用之后还有更多的工作要做，因此编译器无法将其优化为循环，对吧？所以第一个评论应该是答案。如果你把它作为答案，我会标记它。 - Aaron

尾递归优化要求您的下一个函数调用应该恰好是返回表达式。 - Artem Sokolov

2个回答

3

由于尾递归（尾递归优化）的作用。

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

需要注意的是，@tailrec注释并不执行或应用尾递归优化，只是强制编译器在无法进行优化时失败。

而尾递归优化要求您的下一个迭代函数调用应该恰好是返回表达式（不包括其中的其他操作或计算）。

- Artem Sokolov

这本书并没有很清楚地表明这就是为什么有一个辅助函数，尽管它提到了尾调用优化。 - Aaron

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Stef · Accepted Answer

尾递归是一种重要的优化方式，可以加快递归函数的执行速度，并避免递归过深导致的"栈溢出"。

没有尾递归的递归

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。所以我写下一条小注释“记得在计算factorial(8)的结果后乘以9”。

这个过程会一直持续下去；最后我到达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)后，你不需要做任何其他事情！你可以直接返回结果。因此，没有必要保留一个小提示“记得在递归调用之后将结果乘以10”。编译器优化了这种行为：它替换了对go(10, 1)的调用，用go(9, 10)代替。然后，它又用go(8, 90)代替了对 go(9，10) 的调用。因此，在递归过程中，堆栈永远不会增加。这被称为尾递归，因为递归调用是函数执行的最后一件事情（特别地，乘以10是在计算参数时发生的）。