CODEWITHSUNDEEP
algorithmscalarecursiontail-recursion
lolski
lolski

Reputation: 17511

Converting the following function into its tail-recursive form

Basically I have the following algorithm that traverse a graph data structure represented as an edge list.

How do you convert the following recursive function into its tail-recursive form:

def nonTailRec(arg1: Int): Seq[Int] = {
  val dependencies: Seq[Int] = traverse(arg1)
  if (dependencies.size > 0) {
    val b = dependencies.map { dependency => nonTailRec(dependency) }.flatten
    dependencies ++ b
  }
  else {
    Seq()
  }
}

traverse is a function that when given a vertex id, will return Set of vertex IDs directly connected to it.

Upvotes: 0

Views: 118

Answers (1)

Eugene Zhulenev
Eugene Zhulenev

Reputation: 9734

To be able write this function recursively you need to pass current state (accumulated dependencies) and "nodes" that required to check later. Here is my tail-recursive version, but it will fail if you have cycles in your graph, to fix that you need to exclude already visited nodes from "toVisit":

   def traverse(i: Int): Seq[Int] = ???

   def nonTailRec(arg1: Int): Seq[Int] = {
     @tailrec def step(dependsOn: Seq[Int], toVisit: Seq[Int]): Seq[Int] = {
       toVisit match {
         case x :: xs => step(dependsOn :+ x, xs ++ traverse(x))
         case x :: Nil => step(dependsOn :+ x, traverse(x))
         case Nil => dependsOn
       }
     }

     step(Nil, traverse(arg1))
   }

Upvotes: 1

Related Questions