CODEWITHSUNDEEP
scalarecursion
John Doe
John Doe

Reputation: 281

How to make a tail-recursive method which calls itself in a flatMap?

I want to make the following recursive method tail-recursive, but I am not sure if this is even possible, since the method is calling itself inside a flatMap.

@tailrec
def loop(nodes: List[Node], myNodes: List[MyNode]): List[MyNode] = nodes match {
  case Nil => myNodes
  case _ =>
    nodes.flatMap { n =>
      val myNode = MyNode(data = n.data)
      loop(n.getChildNodes().toList, myNode :: myNodes)
    }
}

loop(nodes, List())

Unfortunately, I get the following error:

could not optimize @tailrec annotated method loop: it contains a recursive call not in tail position
[error]           case _ =>
[error]                  ^
[error] one error found

Upvotes: 0

Views: 403

Answers (2)

Cyrille Corpet
Cyrille Corpet

Reputation: 5315

As @SteffenSchmitz said, you cannot make the recursive call inside a flatMap. Indeed, in the case where the list has at least two Nodes, your method will have at least two calls to itself, so it cannot be tailrec. However, you can do the same that your logic is doing here with tail-recursion.

What your code is doing, is copying data in Nodes in nodes which seems to be sone kind of tree structure into a List[MyNode].

In the end, you get the list of all the ancestors for each of the leaves of the original tree.

For instance, if your tree is 

  A
 / \
B   C
   / \
  D   E

You'll get List(B, A, D, C, A, E, C, A) (here, I'm assuming data is a Char, for simplicity). The first B, A are the ancestors for B, the next D, C, A are the ancestors for D, and the last ones for E.

You can do the same with the following tailrec:

@tailrec
def tailrecLoop(nodesWithAncestors: List[(Node, List[MyNode])], acc: List[MyNode]): List[MyNode] = {
  nodesWithAncestors.headOption match {
    case None => acc
    case Some((node, ancestors)) if node.getChildNodes().toList.isEmpty =>
      loop(nodes.tail, acc ::: myNode :: ancestors)
    case Some((node, ancestors)) =>
      val myNode = MyNode(data = node.data)
      val childrenWithAncestors = 
        node.getChildNodes().toList.map(_ -> (myNode :: ancestors))
      loop(childrenWithAncestors ++ nodes.tail, acc)
  }
}

def loop(nodes: List[Node]) = tailrecLoop(nodes.map(_ -> Nil), Nil)

The key here is to put the non-treated nodes (nodesWithAncestors) in a queue, to be handled at some later time by sub-calls.

Upvotes: 4

Steffen Schmitz
Steffen Schmitz

Reputation: 890

It's not possible to make a call inside a flatmap tail-recursive. The last call in your function has to be loop().

Upvotes: 1

Related Questions