Thinking Recursively with Java

Chapter 4. The Procedural Approach

"Well," said Owl, "the customary procedure in such cases is as follows."

"What does Crustimoney Proseedcake mean?" said Pooh. "For I am a Bear of Very Little Brain, and long words Bother me."

"It means the Thing to Do."

"As long as it means that, I don't mind," said Pooh humbly.

—A. A. Milne, Winnie-the-Pooh, 1926

For each of the functions presented in Chapter 3, the necessary recursive decomposition into simpler instances follows directly from the mathematical definition. For example, the Fibonacci sequence is most clearly defined by the recurrence relation

Given this definition, the recursive implementation seems the most natural one, even if it is not the most efficient.

Mathematical formalism, such as the use of recurrence relations, is more easily applied to the domain of recursive functions than to that of recursive procedures, which is the traditional term used for methods that do not return a result. Intuitively, functions are mathematical entities, while procedures are more algorithmic in character. Thus, procedures are less likely to have a simple mathematical formulation, which makes the necessary recursive decomposition of the problem somewhat harder to find. Learning to apply recursive techniques in a procedural context is the essence of thinking recursively and requires a relatively abstract view of procedures themselves.

To the reductionist, ...