Scala sum of a binary tree tail recursive

Question

So I have the following code that define 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 sum method tail recursive?. I suspect is not tail recursive because the calls to right.sumAcc have to wait to left.sumAcc(elem + acc) to terminate.

If its not tail recursive, How can I change it?

http://www.scala-lang.org/old/node/7984 – Millie Smith Oct 22 '14 at 02:12 — Millie Smith, Oct 22 '14 at 02:12

score 3 · Answer 1 · edited May 23 '17 at 12:09

OK, so with the solution pointed out in the comments I rewrite the answer to be tail recursive. I used an accumulator and an implicit stack inside a helper method. And with the annotation we can check that in fact the method is tail recursive.

Here is the new code, just in case someone find it helpful.

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)

score 1 · Accepted Answer · edited May 23 '17 at 12:32

In your case the function is not tail recursive, but the reason is a bit different - there is no waiting, the program is executed sequentially and left.sumAcc is evaluated before right.sumAcc, however this is still a problem, as the left.sumAcc call is recusive, but not in the tail position. Even if you would remove this, there are other problems with your solution.

To check if tail recursion can be applied for the function, you can use the @tailrec annotation. In your case, the compiler error message will be:

Error:(11, 7) could not optimize @tailrec annotated method sumAcc: it is neither private nor final so can be overridden

def sumAcc(acc: Int) = right.sumAcc(left.sumAcc(elem + acc))

Why this happens is explained in Why won't the Scala compiler apply tail call optimization unless a method is final? question:

Unless a method is marked final, it might not be calling itself when it makes a recursive call.

This is also what the compiler will tell you if you try to add final to the NonEmpty sumAcc. The error message will change to:

Error:(11, 38) could not optimize @tailrec annotated method sumAcc: it contains a recursive call targeting supertype NonEmpty.this.right.type

final def sumAcc(acc: Int) = right.sumAcc(left.sumAcc(elem + acc))

The solution linked in the comment by Millie Smith overcomes this by not using overriding to implement the function, pattern matching (i.e. type check in the function) is used instead, therefore one function is handling the traversal for both Leaf and Node types, and the function is structured so that only one call to sumAcc is done in each case.

How is that the program is executed sequentially and there is no waiting? The way that I see it is that `right.sumAcc` have to wait `left.sumAcc`. — edblancas, Oct 22 '14 at 23:00
@edblancas It depends on what you mean by waiting. I understand you may use this word even in sequential execution, when right is executed after left, however to me, waiting indicates parallel execution and one parallel entity waiting for something to happen. — Suma, Oct 23 '14 at 07:05
I get it. But I mean more in the aspect that if there is any danger of stack overflow due to the waiting of the recursive calls. — edblancas, Oct 23 '14 at 15:50
@edblancas Yes, if the call is not tail recursive, there is true recursion and stack overflow can happen with deep enough tree. — Suma, Oct 23 '14 at 17:36

Scala sum of a binary tree tail recursive

2 Answers2