On the other hand, we can observe that $(n−1)! = (n−1)\times \cdots \times1$, so that we can mathematically define factorial in terms of itself:
\begin{split}n! = \begin{cases} 1 &\textrm{if}~ n = 0~ \textrm{or}~ n = 1\\ n \times (n - 1)! &\textrm{otherwise} \end{cases}\end{split}Such a mathematical definition is called a recurrence relation. It translates into code as follows:
1 int factorial(int n) {
2 if (n == 0 || n == 1) {
3 return 1;
4 } else {
5 return n * factorial(n - 1);
6 }
7 }
This function is recursive, since it calls itself as part of its definition (line 5).
Try it out:
The following picture shows how the memory is changing when calling factorial(3):
When the call factorial(3) is evaluated, an activation record is created, and the parameter n is initialized with value 3. The body of factorial() runs, and it calls factorial(2). This creates another activation record, and its parameter n is initialized to 2. Within the context of that activation record, the body of factorial() is executed, and it calls factorial(1). Another activation record is created, with n initialized to 1.
The body runs, returning 1, which replaces the function call in the caller. The activation record for factorial(1) is destroyed, and factorial(2) resumes. The latter computes 2 * 1 and returns 2. The activation record for factorial(2) is destroyed, and factorial(3) continues where it left off. It computes 3 * 2, returning 6. Its activation record is reclaimed, and main() resumes, initializing result to 6, the correct value for $3!$.
Requirements for recursion:
A base case: can be solved without recursion
Recursive cases: break down into subproblems that are similar and smaller (closer to a base case)
A simple analogy for recursion is the Matryoshka.
The recursive code for countDolls() looks like the following:
1 int countDolls(int n) {
2 if (n == 1) {
3 return 1;
4 }
5 else {
6 return 1 + countDolls(n - 1);
7 }
8 }
Try it out:
In its simplest form, a tactile recursive algorithm can be derived to find the smallest doll. If the doll can be opened, then the doll inside can either be opened or not. If it can’t be opened it is the smallest doll. If it can be opened, the process repeats.
The algorithm would look something like this:
Open the doll.
Can the doll inside be opened?
- Yes. Go to Step 1.
- No. It is the smallest doll.
Let us consider another example, that of computing the number of ducks on a duck farm. Suppose the farm starts with five baby ducklings. Assume that a duck lays three eggs each month, once the duck is at least a month old itself. Furthermore, an egg takes a month to hatch, and our ducks never die. How many ducks does the farm have after $n$ months?
We start by working out the first few months by hand. In month 0, there are 5 baby ducklings, which are not old enough to lay eggs. In month 1, there are now 5 grown ducks, each of which lays 3 eggs, resulting in 15 eggs in total. Let’s use a table to keep track of what we have:
| Month | Adult Ducks | Ducklings | Eggs | Total Ducks |
|---|---|---|---|---|
| 0 | 0 | 5 | 0 | 5 |
| 1 | 5 | 0 | 15 | 5 |
| 2 | 5 | 15 | 15 | 20 |
| 3 | 20 | 15 | 60 | 35 |
| 4 | 35 | 60 | 105 | 95 |
| 5 | 95 | 105 | 285 | 200 |
In month 2, the 15 eggs hatch, resulting in 15 ducklings. The 5 adult ducks lay 15 more eggs.
In month 3, these eggs hatch, resulting in 15 ducklings. The previous 15 ducklings are now adults, so that we have a total of 20 adult ducks, which lay 60 eggs.
And so on in months 4 and 5. The total number of ducks is 200 at month 5.
We observe that the number of adult ducks in any particular month is the same as the total number of ducks in the previous month. The number of ducklings in a month is three times the number of adult ducks in the previous month, which is the same as the total number of ducks in the month before. This results in the following recurrence relation for the total number of ducks:
\begin{split}ducks(n) = \begin{cases} 5 &\textrm{if}~ n = 0~ \textrm{or}~ n = 1\\ ducks(n - 1) + 3 \times ducks(n - 2) &\textrm{otherwise} \end{cases}\end{split}The base cases are the first two months, when there are 5 total ducks. (We cannot apply the recurrence for these cases, since it would rely on the number of ducks in month -1, which is ill-defined.)
We can now write a function to compute the number of ducks:
1 int ducks(int n) {
2 // base cases
3 if (n <= 1) {
4 return 5;
5 }
6 // recursive case
7 return ducks(n - 1) + 3 * ducks(n - 2);
8 }
Try it out:
Tail Recursion¶
As a concrete example, the prior recursive implementation of factorial() is not tail recursive, since it does its work in the passive flow:
1 int factorial(int n) {
2 if (n == 0 || n == 1) {
3 return 1;
4 } else {
5 return n * factorial(n - 1);
6 }
7 }
The multiplication must be done after the recursive call returns, so the function is not tail recursive.
For the function to be tail recursive, we need the multiplication to be in the active flow. To do so, we compute $n$ in the initial call to factorial() on $n$, $n \times (n−1)$ in the call on $n−1$, $n \times (n−1) \times (n−2)$ in the call on $n−2$, and so on until we reach 1. At each step, we keep track of the product so far:
1 int factorial(int n, int resultSoFar) {
2 if (n == 0 || n == 1) {
3 return resultSoFar;
4 } else {
5 return factorial(n - 1, n * resultSoFar);
6 }
7 }
Try it out:
However, this is a different interface than our previous versions of factorial(). To retain the same interface, we move the actual computation to a helper function and abstract the call to it:
1 static int factorial_helper(int n, int resultSoFar) {
2 if (n == 0 || n == 1) {
3 return resultSoFar;
4 } else {
5 return factorial_helper(n - 1, n * resultSoFar);
6 }
7 }
8
9 int factorial(int n) {
10 return factorial_helper(n, 1);
11 }
Try it out:
Helper functions are a common pattern for tail-recursive computations that require a seed value. However, not all tail-recursive algorithms require a helper function.
Kinds of Recursion¶
We have now seen several different kinds of recursion.
Linear recursive: A function is linear recursive if it is recursive, but each invocation of the function makes at most one recursive call. Such a function reduces each recursive case to a single subproblem. The various recursive factorial() function above is a linear recursive.
Tail recursive: A function is tail recursive if it is linear recursive, and every recursive call is the last thing that happens in the invocation that makes the recursive call. We have seen both tail-recursive and non-tail-recursive variants of factorial().
Tree recursive: A function is tree recursive if a single invocation of the function can make more than one recursive call. Such a function subdivides a recursive case into multiple subproblems. The ducks() function above is tree recursive. Drawing out the recursive call graph for a tree-recursive function, we end up with a branching structure that resembles a tree, explaining the nomenclature.
Iteration vs. Recursion¶
Iteration and recursion are two approaches to solving complex problems. Conceptually, an iterative algorithm often divides a computation into individual discrete steps, the combination of which forms a solution to the whole problem. In contrast, recursive algorithms generally express a computation in terms of smaller versions of the same problem.
Both iteration and recursion have the same computational power; an iterative algorithm can be converted to a tail-recursive implementation and vice versa. A non-tail-recursive computation can also be rewritten iteratively; however, the iterative version may require explicit storage. The non-tail-recursive algorithm can store data in multiple activation records, while the iterative one only has a single activation record to work with, so it may need an explicit data structure such as a vector to store its data. Techniques such as dynamic programming can be used in general to convert a recursive algorithm to an iterative one, but they are beyond the scope of this course.