A Functional Approach to Java

Chapter 12. Recursion

Recursion is an approach to solving a problem that can be broken down into smaller versions of itself. Many developers see recursion as another—often complicated—approach to iteration-based problem-solving. Still, it’s good to know different techniques for particular groups of problems in a functional way.

This chapter shows the general idea behind recursion, how you implement recursive methods, and their place in your Java code compared to other forms of iteration.

What Is Recursion?

In “Recursion”, you’ve seen an illustration of calculating factorials—the product of all positive integers less than or equal to the input parameter. Many books, guides, and tutorials use factorials to demonstrate recursion because it’s a perfect problem to solve partially, and it’ll be the first example of this chapter, too.

Every step of calculating factorials breaks down into the product of the input parameter and the result of the next factorial operation. When the calculation reaches fac(1)—defined as “1”—the chain terminates and provides the value to the previous step. The complete steps can be seen in Equation 12-1.

Equation 12-1. Formal representation of a factorial calculation

$$\begin{array}{c}fac\left(n\right)\hfill \\ \hfill \to & n*fac(n-1)\hfill \\ \hfill \to & n*(n-1)*fac(n-2)\hfill \\ \hfill \to & n*(n-1)*(n-2)*\cdots *fac\left(1\right)\hfill \\ \hfill \to & n*(n-1)*(n-2)*\cdots *1\hfill \end{array}$$

This generalization of the calculation steps visualizes the underlying concept of recursion: solving ...