Recursively looping trees

[Kai]

I'm trying to recursively loop through a tree where each node can have a left and a right node.

My code looks like this:

    @tailrec

  def sum(node: Tree, acc: Int): Int = node match {

    case Leaf(value) => acc + value

    case Node(value, left, right) => acc + value + Seq(sum(left, 0), sum(right, 0)).max

  }

My problem is that it's not tail recursive.

I can't for the life of me figure out how to build this in a way that it would be. Basically, when you have two recursive calls, how do you make it them a tail call?

Is this even possible?

[Erik Osheim]

On Wed, Mar 12, 2014 at 10:05:27AM -0700, Kai wrote:
> @tailrec
> def sum(node: Tree, acc: Int): Int = node match {
> case Leaf(value) => acc + value
> case Node(value, left, right) => acc + value + Seq(sum(left, 0),
> sum(right, 0)).max
> }

> I can't for the life of me figure out how to build this in a way that it
> would be. Basically, when you have two recursive calls, how do you make it
> them a tail call?
>
> Is this even possible?

To do this without risking a stack overflow exception, you have to
simulate your own stack:

def sum(node: Tree): Int = {
def loop(node: Tree, stack: List[Tree], acc: Int): Int = node match {
case Leaf(n) =>
stack match {
case Nil => acc
case next :: rest => loop(next, rest, acc + n)
}
case Node(n, left, right) =>
loop(left, right :: stack, acc + n)
}
}

In general, when you have problems implementing a tail-recursive
method, you can use this transformation strategy.

-- Erik

P.S. I didn't try compiling this, but I'm pretty sure it works. The
pattern should be obvious.

[Erik Osheim]

And of course, I forgot to call my loop method:

def sum(node: Tree): Int = {
def loop(node: Tree, stack: List[Tree], acc: Int): Int = node match {
case Leaf(n) =>
stack match {
case Nil => acc
case next :: rest => loop(next, rest, acc + n)
}
case Node(n, left, right) =>
loop(left, right :: stack, acc + n)
}

loop(node, Nil, 0)
}

-- Erik

[Erik]

Thanks for the tip!

That code actually does something totally different than what I'm trying to do:

case Node(n, left, right) => 
      loop(left, right :: stack, acc + n) 

I'm trying to add up current value of the node + accumulated value + either sum of left OR sum of right depending on which is greater.

This code, however, iterates 'left' values, pushing 'right' values to stack (to be processed and added later). I don't want to add them both, I want to only add one of them, which is the one that has a greater value.

i.e. if sum(left) > sum(right) then I want value + acc + sum(left) otherwise value + acc + sum(right)

I don't know how to do that comparison / .max() check within that recursive call.

[Paul Keeble]

I try and make as many of my recursive algorithms tail recursive as possible but are you aware how much data your algorithm can handle without being tail recursive? The stack size on the JVM without any tweaking allows a depth of a little over 1000, I would expect you will get at least that. Given that a tree of height 1000 would be pretty big, of the order of 2^1024 which there isn't a computer in this world that can handle that sort of collection size. They can barely cope with 2^32 and 2^64 is beyond anything today so 2^1024 is some way off.

So asuming I have understood everything correctly in your case I would say don't worry about @tailrec. This particular type of problem where you try and find the maximum summation down a height of the tree isn't going to run out of stack space just going down the tree. You mainly get into stack issues with lists and other ways of looking at collections linearly.

PK

--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Erik]

I'm actually not running into stack issues, but rather performance issues. When I have 30+ levels deep tree, it gets really slow.