An introduction to recursion with examples.
In computing, recursion is a general problem solving technique in which the solution to a problem with a given set of input values is defined in terms of solutions to the same problem with a reduced set of input values, or with input values that are smaller in magnitude. By re-invoking with progressively smaller inputs, until we reach some specified stopping condition, we can then incorporate the solutions to the smaller problems into the solutions to the larger problems.
The factorial function (denoted by an exclamation mark after a non-negative integer, or after a symbol representing such an integer) is used in combinatorics, probability, and many other branches of mathematics. It is most often defined as
\[\begin{equation} \label{factorial-iterative} n! = \begin{cases} 1, & \text{when } n = 0; \\ \displaystyle \prod_{i=1}^n i , & \text{when } n \in \{1, 2, \ldots \}. \end{cases} \end{equation}\]In case the $\prod$ symbol is unfamiliar to you, it’s called the product operator, and is used to indicate iterative multiplication. We would read that portion of the the expression above as: “The product, as $i$ varies from 1 to $n$ (inclusive), of $i$.” Without using the product operator, we might write the expression as $(1 \cdot 2 \cdot \ldots \cdot n)$.
Another common definition of the factorial function is recursive. Here, computing $n!$ requires that we first compute $(n - 1)!$:
\[\begin{equation} \label{factorial-recursive} n! = \begin{cases} 1, & \text{when } n = 0; \\ n (n - 1)!, & \text{when } n \in \{1, 2, 3, \ldots \}. \end{cases} \end{equation}\]Following this definition, we might compute $5!$ in the following manner. (Don’t worry about all the parentheses: they’re not necessary for the computation, but they’re useful in the explanation that follows.)
\[\begin{aligned} 5! &= \Bigg (5 \cdot 4! \Bigg ) \\ &= \Bigg (5 \cdot \bigg (4 \cdot 3! \bigg ) \Bigg ) \\ &= \Bigg (5 \cdot \bigg (4 \cdot \Big ( 3 \cdot 2! \Big ) \bigg ) \Bigg ) \\ &= \Bigg (5 \cdot \bigg (4 \cdot \Big ( 3 \cdot \big ( 2 \cdot 1! \big ) \Big ) \bigg ) \Bigg ) \\ &= \Bigg (5 \cdot \bigg (4 \cdot \Big ( 3 \cdot \big ( 2 \cdot \left (1 \cdot 0! \right ) \big ) \Big ) \bigg ) \Bigg ) \\ &= \Bigg (5 \cdot \bigg (4 \cdot \Big ( 3 \cdot \big ( 2 \cdot \left (1 \cdot 1 \right ) \big ) \Big ) \bigg ) \Bigg ) \\ &= \Bigg (5 \cdot \bigg (4 \cdot \Big ( 3 \cdot \big ( 2 \cdot 1 \big ) \Big ) \bigg ) \Bigg ) \\ &= \Bigg (5 \cdot \bigg (4 \cdot \Big ( 3 \cdot 2 \Big ) \bigg ) \Bigg ) \\ &= \Bigg (5 \cdot \bigg (4 \cdot 6 \bigg ) \Bigg ) \\ &= \Bigg ( 5 \cdot 24 \Bigg ) \\ &= 120 \\ \end{aligned}\]Imagine that each set of parentheses represents execution of a computational method for evaluating the factorial function. In order to compute $5!$, we multiply $5$ and $4!$. But in order to compute that, we need to compute $4!$; this adds an inner set of parentheses in the second line. In the third line, we see another set of parentheses, in which we will compute $3!$ (in order to compute $4!$), and so on.
When we get to an expression that includes $0!$, we don’t need to break that term down any further, since our definition tells us that $0! = 1$. (This is a stopping condition.) From that point, we can start completing the computations that are pending: in each of the last 5 lines, we’re replacing a set of parentheses with the result obtained by computing the product inside those parentheses; we can think of this operation as completing execution of one of our factorial computations.
What we’re seeing here is—essentially—the internal workings of computing $5!$ by recursion: each time we replace $m!$ with $(m \cdot (m - 1)!)$, we’re starting a new recursive computation. Each time we replace a set of parentheses with the computed value, we’re completing a recursive computation. Eventually (if we’ve done our job correctly), we have no parentheses left—instead, we have the result, which (in this case) is $120$.
As it turns out, the expression for the factorial function specified in $\eqref{factorial-recursive}$ can be translated to code quite easily—not just Java, but almost any programming language. Even better, the expression in code looks so much like the mathematical expression that it is very easy to verify that the former correctly expresses the latter.
Traditionally, we define a palindrome this way:
A palindrome is a sequence of characters that reads the same forward and backward.
Usually, we qualify this definition a bit, by skipping non-alphanumeric characters (punctuation, whitespace, special symbols like ®, etc.) and ignoring character casing. (As a rule, we also skip subscripts and superscripts, even though they are usually alphanumeric.)
With the qualified definition above, we would consider all of the following to be palindromes:
Somewhat less obviously, we also consider these to be palindromes:
That is, any single character, or even an empty string, reads the same forward and backward, and is thus a (trivial) palindrome.
As we move from the basic definition to code (if, for example, we want to write a method that checks to see if a String specified in a parameter is a palindrome, and return the corresponding boolean result), the latter might look very different from the definition in natural language. But a recursive implementation is often very close to the natural language expression—as long as that natural language expression is also recursive.
Let’s take a new definition as a starting point (ignoring the whole question of whitespace, punctuation, and special symbols for now):
A palindrome is a sequence of characters with:
- a length equal to 0 or 1;
- OR
- the same first and last characters,
- AND a palindrome for the subsequence between the first and last characters (exclusive).
Please note these key points about the definition:
The logical structure (indicated by the indentation and the all-caps words) of the bullets is a Boolean expression, of the form $A$ OR ($B$ AND $C$). We might also write this using special symbols for the logical operators: $A \lor (B \land C)$.
In this context (logical rather than arithmetic), the logical operators should be considered short-circuit operators. When using short-circuit logical operators, the rules about parentheses are modified a bit: In this case, $A$ would be evaluated first; if (and only if) $A$ is false, then we have to evaluate the expression in parentheses.
The definition is recursive. Note the final underlined portion: It is saying that a string is a palindrome if a specified substring is a palindrome. (Of course, that’s only the case if the previous condition—that the first and last characters are the same—is also satisfied.)
Take a few minutes to read and understand the definition. Then try to apply it to one of the palindromes listed above, or any other palindrome that comes to mind. Then, try applying it to a string that’s not a palindrome.
Though the definition specified in $\eqref{palindrome-recursive}$ is more verbose than “a palindrome is a string that reads the same forward and backward,” it’s still reasonably clear; more importantly, it can be translated to code in a very direct fashion, resulting in an implementation that will be easy for us to compare for correctness with the original definition.