Introduction to Recursive Programming

CHAPTER 7

Multiple Recursion II: Puzzles, Fractals, and More...

Calculus, the electrical battery, the telephone, the steam engine, the radio — all these groundbreaking innovations were hit upon by multiple inventors working in parallel with no knowledge of one another.

—Steven Johnson

THE previous chapter introduced divide and conquer algorithms that used multiple recursion and decomposed problems by dividing their size by some constant. Alternatively, this chapter presents solutions to challenging problems that also decompose them into several subproblems, but reduce their size by one or two units. Previous examples of these algorithms are the function in (1.2) that defines Fibonacci numbers, or in (3.2) that can be used to compute binomial ...