Why is tail recursion a poor use of recursion?

Question

I recently studied the date structure. In Mark Allen Weiss's book, Data Structures and Algorithm Analysis in C, Why does he say that tail recursion is a poor use of recursion and it is better not to use it in chapter 3? But I saw how many said it was useful online.

Answer 1

This is not necessarily a bad thing. Tail recursion is always equivalent to a loop, and writing a loop can obviously be more efficient, depending on the compiler. (*) Modern compilers, such as GCC, can optimize tail recursion, but they do not always recognize it. When they do not see this, recursion will consume stack space.

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

When an algorithm has only one recursion, which is 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 assume that we are talking only about C. In some other languages, tail recursion can be considered as a natural loop method (functional languages) or direct abomination (Python).

Answer 2

Tail recursion is a wonderful and completely useful technique for structuring your code. It's not bad. "However, there are some caveats:

• Like any recursion, if your compiler cannot optimize it (check this out), it will consume stack frames. For large input, this can lead to a stackoverflow.

• Some programmers have a childish aversion to recursion and the knowledge that tail recursion can always be converted to a loop; consider that it always should be.

For both of the above reasons, you should learn how to transform between tail recursion and loop, not least because it helps you find out if your compiler can optimize recursion.