Functional and Concurrent Programming: Core Concepts and Features

Chapter 6

Recursive Programming

Loops—the repetition of a code fragment—do not mesh well with functional programming’s emphasis on pure functions, which gain nothing from being repeated. What is needed instead is a mechanism to nest expressions arbitrarily. This mechanism is recursion. Everything that can be computed with loops can be computed using recursion instead (and vice versa). Furthermore, algorithms that are naturally recursive benefit from an implementation that uses recursion directly, which tends to be simpler than the loop-based equivalents. This is especially true of computations that apply to recursive structures, such as lists and trees. Finally, tail recursive functions constitute a class of loop-like recursive functions that ...