Functional Programming in Java, 2nd Edition

Chapter 8Optimizing Recursions

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 optimization (TCO) technique to make recursions feasible for large inputs. Then, we’ll look into ...