尾递归函数（Coursera 问题）

Question

我正在学习 Scala 函数式编程的 Coursera 课程，以便学习这门语言。

他们引入了尾递归函数的概念，并将它们基本上定义为以调用自身结束的函数。但随后他们将其显示为工作示例：

def sum(f: Int => Int)(a: Int, b: Int): Int = {
  def loop(a: Int, acc: Int): Int = {
    if (a > b) acc
    else loop(a + 1, f(a) + acc)
  }
  loop(a, 0)
}

如果我用@tailrec 注释总和，我会得到一个错误，因为 IDE (IntelliJ) 不认为它是尾递归的。

这里sum是叫尾递归，还是内部实现"loop"在这种情况下被认为是尾递归的东西？

Answer 1

内部loop方法是尾递归的，sum方法根本不是递归的。因此，您应该将 loop 注释为 @tailrec.

将 loop 移动到外部范围可能有助于可视化正在发生的事情：

def sum(f: Int => Int)(a: Int, b: Int): Int = {
    loop(a, 0)
}

def loop(a: Int, acc: Int): Int = {
    if (a > b) acc
    else loop(a + 1, f(a) + acc)
}

如您所见，sum 只是 loop 的 public 入口点。

（请注意，上面的代码不会编译，因为 loop 不再关闭 b 或 f，但你明白了。）

Answer 2

你是对的。 sum 需要调用自身，否则 Scala 会抱怨：

@tailrec annotated method contains no recursive calls

如果您通过将 @tailrec 移动到尾递归所在的位置来告诉编译器它的确切位置：

def sum(f: Int => Int)(a: Int, b: Int): Int = {
  @tailrec def loop(a: Int, acc: Int): Int = {
    if (a > b) acc
    else loop(a + 1, f(a) + acc)
  }
  loop(a, 0)
}

然后编译器会满意它是尾递归优化的。

尾递归函数（Coursera 问题）

Tail-Recursive Function (Coursera Issues)

scala

syntax

tail-recursion

higher-order-functions