ABSTRACT
This chapter presents solutions to challenging problems that also decompose them into several subproblems, but reduce their size by one or two units. It discusses how to avoid overlapping subproblems in recursive solutions through an approach known as memorization. The towers of Hanoi Towers of Hanoi puzzle is one of the most popular problems used to illustrate recursion. Although it can be solved using relatively simple iterative algorithms, it also allows a concise and elegant recursive solution that emphasizes the role of problem decomposition and induction in recursion, as well as showing its potential for problem solving. Recursive tree traversals are appealing for their simplicity, and do not require stack or queue data structures as do iterative versions. The chapter considers left-to-right traversals, which process sibling nodes from left to right. The sequence of keys related to a postorder traversal reflects the order in which the associated recursive calls finish.
