Functional Programming – When to Use Tail Recursion?

functional programmingtail-call

I've recently gotten into functional programming. I asked a question earlier over here "'Remembering' values in functional programming" and learned a lot of things I hadn't even realized I wanted to learn yet. It was very useful. It did leave me with a few new unanswered questions. The primary of which is, when should I actually use tail recursion?

In my example, I had inadvertently used it. I was using an example function to raise x to y; x^y.

There's two primary ways that this can be done. A non tail recursive way, as follows:

(the following is all coded in pseudocode)

f(x,y){
   if y > 1,
     return x * f(x,y-1);
   else
     return x;
}

But as an alternative way that is tail recursive, I could do it like this:

f(x,y,z){
   if z == 'null',
     f(x,y,x);
   else if y > 1,
     f(x*z,y-1,z);
   else
     return x;
}

They both work fine, but since the first one is non tail recursive, it could theoretically get hung up on particularly large operations. However, even if that's the case, doing it without tail recursion just feels cleaner. I don't need to use an extra argument, and my code feels very 'mathy.' After all, return x * f(x,y-1) is just another way of saying return x * x^y-1.

I guess what I'm wondering is, are there times when I shouldn't use tail recursion? Is there certain code that is better left without recursion, or should I just make it a habit of recurring all functions when applicable?

Best Answer

First of all, recursion is a measure of last resort in functional programming. Use higher-order functions if it's possible to do so cleanly. I can't emphasize that enough.

That being said, the most common situation to not use tail recursion is when traversing a tree structure, the same situations you use recursion in imperative languages that don't remove tail calls. This is because stack depths are limited to the depth of the tree, and tail recursive versions of those algorithms would be extremely convoluted.

Anything you would use an imperative loop for should be tail recursive: traversing arrays, linked lists, ranges of integers for math calculations, etc.

The exception is if you know the size is bounded. Non tail-recursive functions read a lot better, so you should take advantage of that readability, but be prepared to defend how you know the size is bounded in your code review.

Related Solutions

JVM Tail-Call Optimization – Limitations in Scala and Clojure

Now, I don't know much about Clojure and little about Scala, but I'll give it a shot.

First off, we need to differentiate between tail-CALLs and tail-RECURSION. Tail recursion is indeed rather easy to transform into a loop. With tail calls, it's much harder to impossible in the general case. You need to know what is being called, but with polymorphism and/or first-class functions, you rarely know that, so the compiler cannot know how to replace the call. Only at runtime you know the target code and can jump there without allocating another stack frame. For instance, the following fragment has a tail call and does not need any stack space when properly optimized (including TCO), yet it cannot be eliminated when compiling for the JVM:

function forward(obj: Callable<int, int>, arg: int) =
    let arg1 <- arg + 1 in obj.call(arg1)

While it's just a tad inefficient here, there are whole programming styles (such as Continuation Passing Style or CPS) which have tons of tail calls and rarely ever return. Doing that without full TCO means you can only run tiny bits of code before running out of stack space.

What facility of the underlying virtual machine would allow the compiler to handle TCO more easily?

A tail call instruction, such as in the Lua 5.1 VM. Your example does not get much simpler. Mine becomes something like this:

push arg
push 1
add
load obj
tailcall Callable.call
// implicit return; stack frame was recycled

As a sidenote, I would not expect actual machines to be much smarter than the JVM.

You're right, they aren't. In fact, they are less smart and thus don't even know (much) about things like stack frames. That's precisely why one can pull tricks like re-using stack space and jumping to code without pushing a return address.

Y combinator and tail call optimizations

Do you know of any way in which those two could be reconciled?

No, and with good reason, IMHO.

The Y-combinator is a theoretical construct and is only needed to make lambda calculus turing complete (remember, there are no loops in lambda calculus, nor do lambdas have names we could use for recursion).

As such, the Y combinator is truly fascinating.

But: Nobody actually uses the Y-combinator for actual recursion! (Except maybe for fun, to show that it really works.)

Tail-call optimization, OTOH, is, as the name says, an optimization. It adds nothing to the expresiveness of a language, it is only because of practical considerations like stack space and performance of recursive code that we care about it.

So your question is like: Is there hardware support for beta reduction? (Beta reduction is how lambda expressions are reduced, you know.) But no functional language (as far as I am aware of) compiles its source code to a representation of lambda expressions that will be beta reduced at runtime.

Best Answer

Related Solutions

JVM Tail-Call Optimization – Limitations in Scala and Clojure

Y combinator and tail call optimizations

Related Topic