为什么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

[正如另一个答案所解释的那样，在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
  }
}

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

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

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

Answer 2

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

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

此形状是可能的，因为everything is an expression（某种）。您的def具有一个值，该值由if ... else块定义，其中if和else都具有值，依此类推。如果您想忽略某物的值，则可以在其后放置新行，而块的返回值始终是其中最后一个表达式的值。您可以这样做，以避免必须重写foreach，但是最好改成write it functionally, as a map。