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?

Karl Bielefeldt · Accepted Answer · 2016-10-02T18:31:04.917

11

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.

edited Oct 02 '16 at 18:31

answered Sep 22 '16 at 12:19

Karl Bielefeldt

146,727
38
279
479

Okey dokey, so it would likely be better to use a fold() or a similar derivative? – Ucenna Sep 22 '16 at 14:26
@Ucenna Correct. Fold/reduce, map, etc all encode common recursion patterns. Using them is simpler, less error-prone, and helps other people understand the meaning of your code faster. – Doval Sep 22 '16 at 19:57
1

@Ucenna: In particular, `fold` is *universal*, which means that *everything* which can be done with iteration can also be done with `fold`. And `map`, `filter`, etc. are just special cases of `fold` and can be implemented as a fold, although specialized implementations may be more efficient, and using a more specific operation will make your code easier to read an understand. – Jörg W Mittag Sep 22 '16 at 21:29
"the most common situation to not use tail recursion is when traversing a tree structure": can you elaborate on this and explain why one wouldn't do it? – Giorgio Oct 02 '16 at 17:47
@Giorgio, see my edit. – Karl Bielefeldt Oct 02 '16 at 18:32
@KarlBielefeldt: Thanks. I am trying to find a non convoluted way to do tail-recursive tree traversal. Indeed, it doesn't seem to be easy. – Giorgio Oct 02 '16 at 19:06

score 2 · Answer 2 · answered Sep 22 '16 at 07:30

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.

When to use tail recursion?

2 Answers2