Tail call optimization throwing error on simple function

Question

I have a simple method to build a tree:

    @tailrec final def buildTree (X:DenseMatrix[Double], Y:DenseVector[Double], minBucket:Int):Node = {
        // Get the split variable, split point and data 
        val (splitVar, splitPoint, leftX, leftY, rightX, rightY) = chooseSplit(X, Y, minBucket);
        // If we couldn't find a split, then we have a leaf
        if(splitVar == Double.NegativeInfinity){
            new Node(Y)
        }else{
            // Otherwise recursively build the children and create yourself as a vertex
            val left = buildTree(leftX, leftY, minBucket)
            val right = buildTree(rightX, rightY, minBucket)
            new Node(Y, splitVar, splitPoint, left, right)
        }

However, when I go to compile, I get: could not optimize @tailrec annotated method buildTree: it contains a recursive call not in tail position

I've done things like this in OCaml without any problem at all. Is there a work-around for this?

See the answers to [this question](http://stackoverflow.com/questions/4785502/why-wont-the-scala-compiler-apply-tail-call-optimization-unless-a-method-is-fin). — dfan, Apr 01 '14 at 01:15

Jörg W Mittag · Answer 1 · 2014-04-01T01:33:51.610

1

I think the error message is pretty clear: your method is neither private nor final, therefore it can be overridden, therefore it is not guaranteed that the calls to buildTree will go to the same method. The method needs to be either private or final.

But even if it were private or final, the recursive calls are not in tail position.

Basically, your tail recursive call is neither a tail call nor even guaranteed to be recursive.

edited Apr 01 '14 at 01:33

answered Apr 01 '14 at 01:17

Jörg W Mittag

363,080
75
446
653

Good point, I didn't notice that it's not even theoretically tail recursive. – dfan Apr 01 '14 at 01:19
I've updated the question. This works *without any issues* in OCaml. My question is how to get scala to perform the optimization (which is not that complicated). – dave Apr 01 '14 at 01:22
Well, the strategies for making something tail recursive are well known: add an accumulator, convert to continuation-passing-style, use trampolines, … – Jörg W Mittag Apr 01 '14 at 01:32
@dave When you say it "works without any issues in OCaml, do you mean that OCaml automatically converts your non-tail-recursive function to a version that is tail-recursive? Your function is not tail recursive as written. – dfan Apr 01 '14 at 02:27
@dfan, I'm not entirely sure, hence the question. I know that the function isn't properly tail recursive but more mature, non JVM crippled languages can still make the optimization. – dave Apr 01 '14 at 02:34
1

What optimization? It's not tail recursive, and doesn't make tail calls. What do you think OCaml is optimising, exactly? – The Archetypal Paul Apr 01 '14 at 08:36

Tail call optimization throwing error on simple function

1 Answers1