This Function is Not Tail Recursive

Haven’t read the article, but that would be quite embarrassing.

Anyway, just wanted to add, that tail recursion generally is more efficient than non-tail recursive functions, because ressources don’t have to be maintained over the recursive calls – at least in theory. On the JVM there will be created a new stack frame on each call, because tail recursion is not supported very well. On the other hand, the Scala compiler has tail call optimization and basically would turn the calls into a while loop.

Read my blog post on this topic, if you like http://stronglytypedblog.blogspot.com/2009/08/scala-tail-recursion.html

Perhaps a better way to think of it is that a function is tail recursive if its return value is just the return value of the recursive call. Trying to figure out what the last operation is can be slightly unintuitive, but figuring out that the value of the recursive call gets passed straight through to the original function’s caller is slightly easier to grasp.

Tail recursive functions are not necessarily parallelizeable- consider fold_left (aka reduce, for you lispers). It’s easier to determine if pure functions can be parallelized or not, as the dependencies are explicitly stated as data dependencies. But if a function f uses as an input the output of function g, then f and g are (generally) not parallelizable.

Tail recursion is a compiler optimization, so what matters isn’t whether or not the last call is a simply function call or a function call as part of a bigger expression, but rather if the compiler can optimize a tail recursive call out of the code _period_.

Scala specifically, due to limitations of the JVM, cannot optimize away the example code you provided — very true. And it’s almost certainly better to write it the second way to be sure.

Just wanted to point out that it’s the compilers job to make it tail recursive in the first place, and so it’s ability to do that will vary by language.

One of the nice things about lisp-like languages (or any non-infix one, really) is that the mistake would’ve been obvious from the beginning since instead of “n * fac(n -1)” it would be written “(* n (fac (- n 1)))” and you would clearly see that there’s another function outside fac.

Not only is there @tailrec, but these days it’s very specific about how you blew it. Since there’s no preview and I have no idea what markup options I have this will probably be a mess, but:


scala> import annotation._
import annotation._

scala> @tailrec def fac(n: Int): Int = if (n==0) 1 else n * fac(n-1)
:8: error: could not optimize @tailrec annotated method: it contains a recursive call not in tail position
@tailrec def fac(n: Int): Int = if (n==0) 1 else n * fac(n-1)
^


@stephan: I think you just misunderstood what I said and then just rephrased my point :)

@stephan: it is certainly possible to write a compiler/interpreter which does not perform tail call optimisation on any of your examples. One reason to do so might be to output full stack traces, including those frames which could be discarded through tail call optimisation to aid debugging. So, whether a tail call is made is very much influenced by the compiler.

However, the ease with which a function may be optimised is, as you say, a property of the function itself.

@stephan: He’s demonstrating it was slower than iterating over a mutable structure, not that it’s slower than unoptimized recursion. This leaves you with no apparent point. I can’t think of any scenario in scala where transforming a tail call into a jump could slow it down compared to not doing so.

There is also a great post from John Rose about tail calls support in JVM http://blogs.sun.com/jrose/entry/tail_calls_in_the_vm and I hope there is something on the way to Java 7 that is going to be useful.

In practice I live by the following definition: It’s tail recursive if there is no return point in the function that requires the current stack frame to be kept around until the recursive call returns. Beyond this one only needs to know if one’s compiler is clever enough to actually notice this and do something smart about it (like turning the tail recursive function application into a loop).

Oh, and it has about nothing to do with being parallelizable except that tail-recursive functions often tend to be referentially transparent, too, and therefore are memoizable (can be cached).