Introduction to Recursive Programming

CHAPTER 6

Multiple Recursion I: Divide and Conquer

Δ ι α ι ´ ρ ε ι κ α ι β α σ ι ´ λ ε υ ε (divide and conquer).

—Philip II of Macedon

THE advantages of recursion over iteration, such as code clarity or avoiding managing a stack explicitly (see Section 10.3.5), are mainly due to the possibility of using multiple recursion. Methods based on this type of recursion invoke themselves several times in at least one recursive case. Therefore, these algorithms solve more than one simpler self-similar problem, and must combine, extend, and/or modify their results in order to obtain the solution to the original problem.

The book devotes three chapters to multiple recursion, and contains additional examples throughout it as well. In this ...