为什么 Scala 无法将此函数编译为尾递归？

Question

如果我将以下递归深度优先搜索函数的第一行替换为在 foreach 块中注释掉的行，它将无法编译为尾递归函数（由于 @tailrec 注释），即使递归显然仍然是函数的最后一个动作。这种行为有正当理由吗？

@tailrec def searchNodes(nodes: List[Node], visitedNodes: List[Node], end: String, currentLevel: Int) : Int = {
    if (nodes.exists(n => n.id == end)) return currentLevel
    val newVisitedNodes = visitedNodes ::: nodes
    var nextNodes = List[Node]()
    nodes.foreach(n => {

        /*
        if (n.id == end){
            return currentLevel
        } 
        */
        nextNodes = nextNodes ::: n.addAdjacentNodes(visitedNodes)
    })
    if (nextNodes.size == 0) return -1
    return searchNodes(nextNodes, newVisitedNodes, end, currentLevel + 1)
}

Answer 1

我不确定编译器到底在想什么，但我认为你所有的 return 语句 will be causing problems.

使用 return 是 scala 中的反模式 - 您不需要编写它，也不应该。为避免这种情况，您必须将 if ... return 块重组为 if ... value ... else ... other value 块。

这个形状是可能的，因为 everything is an expression (sort of). Your def has a value, which is defined by an if ... else block, where the if and the else both have values, and so on all the way down. If you want to ignore the value of something you can just put a new line after it, and the return value of a block is always the value of the last expression in it. You can do that to avoid having to rewrite your foreach, but it would be better to write it functionally, as a map.

Answer 2

正如另一个答案所解释的那样，在 scala 中使用 return 是一个坏主意，也是一种反模式。但是 更糟糕的是 是在 lambda 函数中使用 return（就像您在 foreach 中注释掉的代码）：这实际上会引发异常，那就是抓住外面使主要功能退出。

因此，您的函数主体被编译成如下内容：

def foo(nodes: List[Node]) = {
  val handle = new AnyRef
  try {
     nodes.foreach { n => 
       if(n.id == "foo") throw new NonLocalReturnControl(handle, currentLevel)
     ...
     foo(nextNodes)
  } catch {
     case nlrc: NonLocalReturnControl[Int] if nlrc.key == handle => nlrc.value
  }
}

如您所见，您的递归调用不在此处的尾部位置，因此编译器错误是合法的。

一个更惯用的写你想要的方法是解构列表，并使用递归本身作为循环的"engine"：

def searchNodes(nodes: List[Node], end: String) = {
  @tailrec def doSearch(
    nodes: List[(Node, Int)], 
    visited: List[Node], 
    end: String
  ) : Int = nodes match {
    case Nil => -1
    case (node, level) :: tail if node.id == end => level
    case (node, level) :: tail => 
      doSearch(
        tail ::: node.addAdjacentNodes(visited).map(_ -> level+1),
        node :: visited,
        end
      )
  }

  doSearch(nodes.map(_ -> 0), Nil, end)
}

为什么 Scala 无法将此函数编译为尾递归？

Why does Scala fail to compile this function as tail recursive?

scala

recursion

tail-recursion