Introduction to Recursive Programming

CHAPTER 11

Tail Recursion Revisited and Nested Recursion

One should always look for a possible alternative, and provide against it. — Sherlock Holmes

—Arthur Conan Doyle

TAIL recursion is special due to its relationship with iteration. Firstly, it is fairly straightforward to transform tail-recursive algorithms into analogous iterative versions that are not only more efficient, but will not be liable to stack overflow errors. Thus, for some programmers, tail recursion is actually considered to be a bad practice. Furthermore, it is not uncommon to encounter tail-recursive algorithms that have been designed by using an imperative approach that is closer to iterative thinking than to problem decomposition and induction. In these cases iterative ...