Why tail-recursion is a bad use of recursion?

Question

I recently in learning Date structure. In Mark Allen Weiss's book , Data structures and Algorithm Analysis in C , Why he says tail-recursion is a bad use of recursion and best not use it in chapter 3 ? But I saw many people say it is useful online.

Answer 1

It's not necessarily bad. Tail recursion is always equivalent to a loop and writing the loop explicitly can be more efficient, depending on the compiler.(*) Modern compilers such as GCC can optimize tail recursion away, but they don't always recognize it. When they don't see it, the recursion will consume stack space.

That said, an algorithm such as quicksort is naturally expressed recursively and one of its two recursions is a tail recursion. I'd write it recursively on a first pass and then rewrite it as a loop if I found that it was too slow.

When an algorithm has only a single recursion that is a tail recursion, it might still be a good idea to write it as a loop right away, because recursive functions can be harder to debug than loops.

(*) I'm assuming we're talking about C only. In some other languages, tail recursion can be either considered the natural way of looping (functional languages) or an outright abomination (Python).

Answer 2

Tail recursion is fine, and a perfectly useful technique to structure your code. It is not "bad". However, there are some caveats:

1. Like any recursion, unless your compiler can optimise it away (check this), it will consume stack frames. For large input, this may lead to a stackoverflow.

2. Some programmers have a childish revulsion to recursion, and knowing that tail-recursion can always be transformed to a loop, believe it always should be.

For both of the above reasons, you should learn how to transform between a tail recursion and a loop, not least because it will help you know if your compiler can optimise away the recursion.