avoiding a for loop to reach a tail recursive state in scala

Question

I have written the following method to print an arbitrary arity tree structure. (deep first search)

def treeString[A](tree: Tree[A]): String = {

  def DFS(t: Tree[A], acc: String = "", visited: List[String] = Nil, toClose: Int = 0): String = t match {
    case Leaf(id, terminal) if !visited.contains(id) => {
      acc + " " + terminal.name + "[" + id.toString + "] " + ")"*toClose
    }
    case Node(id, op, args @_*) if !visited.contains(id) => {
      var state = acc + " " + op.name + "[" + id.toString + "] " + "("
      var args_visited: List[String] = List(id)
      for (i <- args.tail) {
        state = DFS(i, state , visited ::: args_visited) + " , "
        args_visited = args_visited ++ List(i.id)
      }
      DFS(args.head, state , visited ++ args_visited, toClose + 1)
    }
    case _ => acc
  }
  DFS(tree)
}

The scala compiler claims this function is not tail recursive. However at the tail position i have the proper DFS(..) call. All of the DFS(..) calls made in the loop will be done in an iterative fashion, thus stack safe.

I understand that if the tree is infinitely deep a stack overflow will occur. Do we have a technique to deal with these cases?

Answer 1

I have to agree with @VictorMoroz. The problem is that your statement:

state = DFS(i, state , visited ::: args_visited) + " , "

is not in the tail position. It does create a new stack, thus, your method is not tail recursive anymore.

Without deep dive into your data structures, here the way to tail-recursive-traverse a tree in DFS manner.

sealed trait Tree[+A]
  case class Leaf[A](value: A) extends Tree[A]
  case class Node[A](left: Tree[A], right: Tree[A]) extends Tree[A]
  case class Element(id:Int, name:String)


  def DFS[T](t:Tree[T]): List[Element] = {
    @tailrec
    def _dfs(rest:List[Tree[T]], visited:List[Element]):List[Element] = {
      rest match {
        case Leaf(v:Element) =>  v :: visited  

        case Node(l,r) :: rs => _dfs(l::r::rs,visited)

      }
    }
    _dfs(List(t),Nil)
  }

The key is to use an explicit stack - here in form of a List.

I understand that if the tree is infinitely deep a stack overflow will occur.

This is correct. Basically, in the most programming languages, each method call reserve some of the stack memory. In simple words tail-recursion allow the compiler to ignore the previous state - do not need the previous stack.

Bare in mind that DFS can not ensure to find the global optima and should not be used if this should be fulfilled.

Postscriptum: The @tailrec annotation is a friendly hint on the compiler to check in compile time whether your method can be optimized or not (Scala do tail-call optimization by default).

Answer 2

I managed to reach a tail recursive state.

Despite the elegancy of the code i truly question the cost/benefit of a functional approach. Most of the times it is not obvious how to manually pass the stack through the algorithm.

Anyway, the true problem here resides in the JVM's recursiveness problems, the scala compiler stills tries to provides us an escape with the tail recursive feature, but it is often a nightmare to put things working

def treeString[A](tree: Tree[A]): String = {

  def dropWhile[A](l: List[A], f: A => Boolean): List[A] =
    l match {
      case h :: t if f(h) => dropWhile(t, f)
      case _ => l
    }

  @tailrec
  def DFS(toVisit: List[Tree[A]], visited: List[String] = Nil, acc: String = "", n_args: List[Int] = Nil): String = toVisit match {
    case Leaf(id, terminal) :: tail if !visited.contains(id) => {
      val n_args_filtered = dropWhile[Int](n_args, x => x == 1)
      val acc_to_pass = acc + " " + terminal.name + "[" + id.toString + "] " + ")" * (n_args.length - n_args_filtered.length) + "," * {if (n_args_filtered.length > 0) 1 else 0}
      val n_args_to_pass = {if (n_args_filtered.length > 0 )List(n_args_filtered.head - 1) ::: n_args_filtered.tail else Nil}

      DFS(toVisit.tail, visited ::: List(id), acc_to_pass, n_args_to_pass)
    }
    case Node(id, op, args @_*) :: tail if !visited.contains(id) => {
      DFS(args.toList ::: toVisit.tail, visited ::: List(id), acc + " " + op.name + " (", List(args.length ) ::: n_args)
    }
    case Nil => acc
  }
  DFS(List(tree))
}