Recurrence relations and other problem domains tp which recursion is applicable
Some mathematical sequences are defined (at least in part) according to a recurrence relation between the terms of the sequence. In this type of definition, the value of the $n^\text{th}$ term of a sequence is defined as a function of the preceding terms. This type of definition is often used for infinite sequences.
Given the sequence $A$, where
\[\begin{aligned} A &= \left( a_0, a_1, \ldots \right), \end{aligned}\]a recurrence relation may be defined (in very general terms) as
\[\begin{aligned} a_n &= f\left( a_0, a_1, \ldots, a_{n-1} \right). \end{aligned}\]In practice, the function $f$ usually isn’t expressed as a function of all the preceding terms, but of a small number of terms immediately preceding $a_n$. Also, note that the recurrence relation usually doesn’t define $A$ completely: the definition generally includes one or more initial values, as well.
The most widely known examples of recurrence relations are probably the factorial function and the Fibonacci sequence.
Problems that can be defined using recurrence relations are prime candidates for recursive implementations.
Recursion isn’t limited to evaluating mathematical functions. Many problems that are not strictly mathematical in nature can be specified in recursive terms, with potential for recursive implementation. The most widely used sorting algorithms are usually implemented in recursive forms. A depth-first search in a tree data structure is easily implemented as a recursive operation. A number of puzzles, such as the Tower of Hanoi, can best be understood in recursive terms. The task of parsing (for compilation) the source code of many programming languages is often specified and implemented as a recursive process. Even processing natural language is at least partially a recursive task.
Even though these problems aren’t obviously mathematical, they have a conceptual structure similar to that of recurrence relations in mathematics—namely, that the solution to a problem can be expressed in terms of solutions to smaller versions of the same problem.
For example, we can articulate the process of sorting a collection of values as follows:
If the collection is trivial, containing 0 or 1 values, then the task is done.
Otherwise,
- Divide the collection into 2 or more sub-collections.
- Sort the sub-collections.
- Merge the sorted sub-collections into a sorted collection.
(Notice that step 2 is recursive.) Of course, this isn’t really an algorithm, as written here, but more a meta-algorithm. Steps 1 & 3 can be performed many different ways: the quicksort algorithm (for example) does a lot of processing in step 1, and virtually none in step 3; mergesort, on the other hand, does most of its work in step 3, but almost none in step 1.
The last paragraph of each of the examples points out some of the key benefits of recursion:
If we have a problem that can expressed fairly simply (in natural language) in recursive terms, then going from that to a recursive implementation is often significantly simpler than going from a non-recursive expression of the problem to a non-recursive implementation.
When going from a recursive definition in a natural language to a recursive implementation in a programming language, verifying the resulting code for correctness is usually easier than when using non-recursive definitions and implementations.
It is often the case that a recursive implementation—especially a naïve one—may not be the best option, however elegant its expression. The main disadvantages of recursion (apart from the difficulty we might have in wrapping our heads around the concept at first) have to do with the time cost of method invocation and the space cost of (and limits on) stack space.
In Java (and many other languages), recursive method invocation is—just as the name implies—method invocation. That means that each invocation add a stack frame to the stack and requires a small amount of processing time for the invocation itself.
With some language/compiler combinations, if the recursive implementation is written in a particular fashion, the compiler is able to compile the recursive code into an iterative form in the byte code or machine code; this is called tail recursion elimination. Currently, Java does not do that—though the compilers for some other languages running on the JVM, such as Scala, do. In any case, this does require that our code is written in a very specific way. (It can be proven that any recursive implementation can be transformed into an iterative one. However, performing such a transformation isn’t a trivial process, in general.)
If there’s a closed-form expression (i.e. one that does not depend on recurrence) for a computation, an implementation based on that may be more time-efficient than a recursive approach; it will almost certainly be more memory-efficient, especially for large problems. This is particularly true when using a compiler that doesn’t implement tail recursion elimination. Note that in some cases fitting into this category, we still might use a recursive approach, if the size of the problem is constrained so that we’re not concerned about stack space.
When using recursion, we have to be even more careful than usual with stopping conditions. Notice that both of our example recursive definitions have stopping conditions: in the factorial case, if $n = 0$, we don’t have to perform any recursive evaluation; in the palindrome case, if the string length is 0 or 1, there’s no need for recursive evaluation. If, in our implementations, we were to check for our stopping conditions after we perform recursion (or not check them at all), we’d never reach our stopping conditions, and the evaluation would never terminate (at least not in a useful fashion).
In an iterative implementation, bad or missing stopping conditions can result in an infinite loop—but the virtual machine doesn’t terminate. Code on other threads will continue to run; if those threads are running on on other CPUs or cores, they might not even be affected that much.
On the other hand, bad or missing stopping conditions in a recursive implementation will most often result in stack memory being exhausted (in Java, this causes a StackOverflowError). In the best case, this won’t cause the JVM to terminate (since each thread has its own stack)—but it quite often does.
In some naïve implementations, the number of recursive invocations increases disproportionately as the problem size increases. This may be caused by overlapping subproblems, where we re-solve subproblems that we’ve already solved—sometimes many, many times. For example, we see this problem in naïvely recursive computations of Fibonacci numbers. In such cases, we might switch to a non-recursive implementation—or we might keep the recursion, but use memoization to avoid recomputing values we’ve already computed.