Functional Programming in Java

Chapter 7Optimizing Recursions

Divide each difficulty into as many parts as is feasible and necessary to resolve it.

René Descartes

Recursion is a powerful and charming way to solve problems. It’s highly expressive—using recursion we can provide a solution to a problem by applying the same solution to its subproblems, an approach known as divide and conquer. Various applications employ recursion, such as for finding the shortest distances on a map, computing minimum cost or maximum profit, or reducing waste.

Most languages in use today support recursion. Unfortunately, problems that truly benefit from recursion tend to be fairly large and a simple implementation will quickly result in a stack overflow. In this chapter we’ll look at the tail-call ...