Recursion

We introduce the recursive paradigm and revise some of the problems discussed in the previous chapters, giving new recursive algorithms for them. To understand the profound meaning of the paradigm, the classic Tower of Hanoi problem is studied in some detail proving upper and lower bounds on its computational cost. Finally, we discuss when and how the recursive approach is beneficial, showing that an inappropriate application of the paradigm may lead to serious negative consequences.