ABSTRACT
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 versions are clearly superior. This chapter examines this connection between tail-recursion and iteration. It provides a brief introduction to nested recursion, and a strategy for deriving simple tail-recursive algorithms, often analogous to iterative methods, but by using a declarative approach. In general, recursive algorithms can be converted into equivalent iterative versions by using a stack data structure that plays the role of the program stack.
