When to use tail recursion?

Question

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?

Answer 1

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.

Answer 2

That depends on how much you value efficient processing without the risk of stack overflow versus readability. And also on whether you find recursion and accumulators a bit weird, perfectly weird, or perfectly normal.

In other words, the trade-off concerns subjective qualities, which is why there is no generally accepted answer. Note also that the more you use a feature, the more natural it will come to appear to you, which is great for you working with your own code base, but potentially worse for others having to work with it.