为什么 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在 scala 中使用是一个坏主意，也是一种反模式。但更糟糕的是return在 lambda 函数内部使用（就像你在里面注释掉的代码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
  }
}

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

编写您想要的内容的一种更惯用的方法是解构列表，并将递归本身用作循环的“引擎”：

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