Scala binary tail tail sum recursive
So I have the following code defining a binary tree.
sealed abstract class BinTree {
def sum = sumAcc(0)
def sumAcc(acc: Int): Int
}
case class NonEmpty(val elem: Int, val left: BinTree, val right: BinTree) extends BinTree {
def sumAcc(acc: Int) = right.sumAcc(left.sumAcc(elem + acc))
}
case object Empty extends BinTree {
def sumAcc(acc: Int) = acc
}
val rootTree = NonEmpty(1, NonEmpty(2, NonEmpty(3, Empty, Empty), Empty), Empty)
rootTree.sum
Is the method sum
tail recursive ?. I suspect this is not tail recursion because the calls right.sumAcc
have to wait for completion left.sumAcc(elem + acc)
.
If its not tail recursive, how can I change it?
source to share
In your case, the function is not tail-recursive, but the reason is slightly different - there is no wait, the program is executed sequentially, but left.sumAcc
evaluates to right.sumAcc
, however, this is still a problem, since the call left.sumAcc
is returnable, but not at the tail position. Even if you remove this, there are other problems with your solution.
To check if head recursion can be applied to a function, you can use the @tailrec annotation . In your case, the compiler error message would be:
Error: (11, 7) failed to optimize @tailrec annotated method sumAcc: it is neither private nor final, so it can be overridden
def sumAcc (acc: Int) = right.sumAcc (left.sumAcc (elem + acc))
Why this happens is explained in Why doesn't the Scala compiler apply tail-call optimization unless the method is final? question:
If a method is not marked final, it may not call itself when it makes a recursive call.
This is also what the compiler will tell you if you try to add final to NonEmpty
sumAcc
. The error message will change to:
Error: (11, 38) Failed to optimize @tailrec sumAcc annotated method: it contains recursive call targeting supertype NonEmpty.this.right.type
final def sumAcc (acc: Int) = right.sumAcc (left.sumAcc (elem + acc))
the solution linked in Millie Smith's comment overcomes this by not using overriding to implement the function, instead using pattern matching (i.e. type checking in a function) so one function handles traversal for the types Leaf
and Node
and the function is structured so that only one the call sumAcc
is made in every case.
source to share
OK, so with the solution pointed out in the comments, I am rewriting the answer to be recursive. I used accumulator and implicit stack inside helper method. And with the help of annotation, we can check that in fact the tail method is recursive.
Here is some new code, in case anyone finds it useful.
import scala.annotation.tailrec
sealed abstract class BinTree
case object Empty extends BinTree
case class NonEmpty(val elem: Int, val left: BinTree, val right: BinTree) extends BinTree
val rootTree = NonEmpty(1, NonEmpty(2, NonEmpty(3, Empty, Empty), Empty), Empty)
def sumTailRec(bt: BinTree) = {
@tailrec
def sumAccStack(trees: List[BinTree], acc: Int): Int = trees match {
case Nil => acc
case Empty :: rs => sumAccStack(rs, acc)
case NonEmpty(e, l, r) :: rs => sumAccStack(l :: r :: rs, e + acc)
}
sumAccStack(List(bt), 0)
}
sumTailRec(rootTree)
source to share