CODEWITHSUNDEEP
scalarecursiontail-recursion
ktam33
ktam33

Reputation: 1247

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

If I replace the first line of the following recursive depth first search function with the lines commented out within the foreach block, it will fail to compile as a tail recursive function (due to the @tailrec annotation) even though the recursion is still clearly the last action of the function. Is there a legitimate reason for this behavior? 

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

Upvotes: 0

Views: 231

Answers (2)

Dima
Dima

Reputation: 40500

As the other answer explains, using return in scala is a bad idea, and an anti-pattern. But what is even worse is using a return inside a lambda function (like your commented out code inside foreach): that actually throws an exception, that is then caught outside to make the main function exit.

As a result, the body of your function is compiled into something like: 

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

As you can see, your recursive call is not in a tail position here, so compiler error is legit.

A more idiomatic way to write what you want would be to deconstruct the list, and use the recursion itself as the "engine" for the loop:

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

Upvotes: 5

gandaliter
gandaliter

Reputation: 10101

I'm not sure exactly what the compiler is thinking, but I think all your return statements will be causing problems.

Using return is an antipattern in scala - you don't need to write it, and you shouldn't. To avoid it, you'll have to restructure your if ... return blocks as if ... value ... else ... other value blocks.

This shape is possible because 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.

Upvotes: 3

Related Questions