Tail recursive functions for BinaryTree

Question

I am stuck with implementing tail recursive foreach, reduce, map and toList functions for a very simple implementation of binary tree.

sealed trait Tree[+A]
case object EmptyTree extends Tree[Nothing]
case class Node[A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A]

object Tree {

  def apply[A]: Tree[A] = EmptyTree
  def apply[A](value: A): Tree[A] = Node(value, EmptyTree, EmptyTree)
  def apply[A](value: A, left: Tree[A], right: Tree[A]): Tree[A] = Node(value, left, right)

  def foreach[A](tree: Tree[A], f: (A) => Unit): Unit = {
    //@tailrec
    def iter[A](tree: Tree[A], f: (A) => Unit): Unit = tree match {
      case EmptyTree =>
      case Node(v, l, r) =>
        iter(l, f)
        f(v)
        iter(r, f)
    }
    iter(tree, f)
  }

  def reduce[A](tree: Tree[A], value: A, f: (A, A) => A): A = {
    //@tailrec
    def loop(tree: Tree[A], value: A): A = tree match {
      case Node(v, l, r) => loop(l, f(loop(r, value), v))
      case EmptyTree => value
    }
    loop(tree, value)
  }

  def map[A, B](tree: Tree[A], f: A => B): Tree[B] = {
    //@tailrec
    def iter[A](tree: Tree[A], f: A => B): Tree[B] = tree match {
      case Node(v, l, r) => Node(f(v), iter(l, f), iter(r, f))
      case EmptyTree => EmptyTree
    }
    iter(tree, f)
  }

  def toList[A](t: Tree[A]): List[A] = {
    //@tailrec
    def iter[A](t: Tree[A]): List[A] = t match {
      case Node(v, l, r) => v :: iter(l) ::: iter(r)
      case EmptyTree => List.empty
    }
    iter(t)
  }
}

Code for testing:

val tree = Tree(1, Tree(2, Tree(3), Tree(4)), Tree(5, Tree(6), Tree(7)))
Tree.foreach(tree, (x: Int) => println(x))
Tree.reduce(tree, 0, (x: Int, y: Int) => x + y)
Tree.map(tree, (x: Int) => x + 1)
Tree.toList(tree)

I cant use @tailrec attribute because as you can see, recursive calls are not the last calls in a function, and I do not know how to rewrite it because there are several calls in one function, for example

v :: iter(l) ::: iter(r)

I know that I can use accumulator for inner recursive functions but how I should use it in case of several calls ?

Thanks in advance.

Updated:

def toListRec[A](tree: Tree[A]): List[A] = {
  @tailrec
  def iter(result: List[A], todo: List[Tree[A]]): List[A] = todo match {
    case x :: tail => x match {
      case Node(v, l, r) => iter(v :: result, l :: r :: tail)
      case EmptyTree => iter(result, tail)
    }
    case Nil => result.reverse
  }
  iter(List.empty, List(tree))
}

Answer 1

Without tail recursion, a(/the) stack is used to keep track of calling functions. If you want to use tail recursion, you'll have to find a way to keep track of this information elsewhere. In simpler "linear" cases, such as factorial, this information is pretty limited and can often easily be taken care of by using an accumulator.

In your case, the problem is that the recursion isn't linear. After one recursive call, the function doesn't just compute the result, but it makes another recursive call before being able to get to the result.

In order to apply tail recursion in this case, you will have to explicitly keep track of the remaining recursive calls that have to be made. An easy way is to simply keep a "to-do" list. For example:

def toList[A](t: Tree[A]): List[A] = {
  @tailrec def iter[A](todo: List[Tree[A]], r: List[A]): List[A] =
  todo match {
    case t :: rest => t match {
      case Node(v, l, r) => iter(l :: r :: rest,  v :: r)
      case EmptyTree => iter(rest, r)
    }
    case List.empty => reverse(r)
  }
  iter(List(t), List.empty)
}

Disclaimer: I know nothing about scala. :)