尾递归函数(Coursera问题)

Question

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

他们引入了尾递归函数的概念，并将其定义为以调用自身结束的函数。但是，他们把这作为一个有效的例子：

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

如果我用@ tail get注释sum，就会得到一个错误，因为IDE (IntelliJ)并不认为它是尾递归的。

这里是所谓尾递归的和，还是内部实现“循环”在这里被认为是尾递归的东西？

Answer 1

你是对的。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)
}

然后编译器将满足它是尾递归优化。

Answer 2

内部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的一个公共入口点。

(请注意，上面的代码不会编译，因为loop不再在b或f上关闭，但您明白了。)