How to break this curse by a pure functional recursive function? I have written two programs to find out a loopy path in a directed graphs.

The first version is a pure functional recursive solution, but its complexity is exponential. The second version following it achieves a linear complexity, but it doesn't look perfect either.

 def GetACycle(start: String, maps: Map[String, List[String]]): List[String] = {

    def explore(node: String, visits: List[String], steps: Int): List[String] = {
      println(List.fill(steps)("\t").mkString + node)
      if (visits.contains(node)) (visits.+:(node)).reverse
      else {
        if (maps(node).isEmpty) Nil
        else {
          val id = maps(node).indexWhere(x =&gt; !explore(x, visits.+:(node), steps + 1).isEmpty)
          if (id.!=(-1))
            explore(maps(node)(id), visits.+:(node), steps + 1)
          else
            Nil
        }
      }
    }

    explore(start, List(), 0)
  }


The second version uses mutable variables, the "visits" and "path", though it achieves a linear complexity in terms of number of visited nodes. 

Would it be possible to achieve such a linear complexity in this situation while using a pure functional recursion without any mutable variables?

  def GetACycle2(start: String, maps: Map[String, List[String]]): List[String] = {
val nodes = maps.:\(Set[String]())((item, set) =&gt;
  item._2.:\(set)(((i, set) =&gt; set.+(i))).+(item._1))
val pairs = nodes.toList.zip(List.fill(nodes.size)(false))

var visits = pairs.toMap
var path = List[String]()

def explore(node: String, steps: Int): Boolean = {
   println(List.fill(steps)("\t").mkString + node)
  path = path.+:(node)
  if (visits(node)) { visits = visits.updated(node, true); true }
  else {
    visits = visits.updated(node, true)
    if (maps(node).isEmpty) false
    else {
      maps(node).exists( x =&gt; explore(x, steps+1))
    }
  }
}

explore(start, 0)
path


}
What about something like this (Please excuse my style/form - As with the other poster, I'm not very familiar with coding in Scala either):

def GetACycle(start: String, maps: Map[String, List[String]]): List[String] = {

//entry function
def explore(node: String): List[String] = {
    explore_r(node, List(), List())
}

//main recursive
def explore_r(node: String, visited: List[String], path: List[String]): List[String] = {
    println(node)
    if (!maps.contains(node)) return Nil
    if (visited.contains(node)) return path++List(node)
    val branches = maps(node)
    for (nextnode &lt;- branches){
        val loop = explore_r(nextnode, visited++List(node), path++List(node))
        if (loop != Nil) return loop
    }
    Nil
}
explore(start)
}