Chapter 11: Recursion
For the first ten years or so of high-level programming, a method was not allowed to call itself. The early versions of FORTRAN, the language most scientific computing was written in during the 1950s, set aside one fixed block of memory for each subroutine. That block held the subroutine’s variables and the address it had to return to when it finished. The arrangement was simple and fast, and it had one consequence nobody could argue with: if a subroutine called itself, the second call would overwrite the first call’s return address, and the program would never find its way home.
When the ALGOL 60 language was designed, its authors decided that a procedure should be allowed to call itself. That decision moved the difficulty from the language to the people writing the compiler. In Amsterdam in 1960, Edsger Dijkstra and Jaap Zonneveld built the first working ALGOL 60 compiler, and the mechanism that made self-calling procedures possible was a stack: instead of one fixed block per method, the machine kept a growing pile of blocks, one for each call still waiting to finish. Dijkstra described the idea in a short paper called Recursive Programming the same year.
Every recursive method you write in Java rests on that pile. Recursion is the technique of solving a problem by solving a smaller version of the same problem, as suggested in Fig. 11.0-1.
Diagram
Fig. 11.0-1 – a set of five nested rounded boxes drawn one inside the next, labelled from the outside in “solve for n”, “solve for n-1”, “solve for n-2”, “solve for n-3”, “solve for 1”; the innermost box shaded and marked “answer known directly”; a curved arrow along the left side pointing inwards labelled “each call passes a smaller problem”, and a curved arrow along the right side pointing outwards labelled “each answer is passed back”
Work through this chapter and you will be able to answer all five.
11.1 Thinking About a Problem in Terms of Itself
Most of the methods you have written so far solve a problem by working through it. A loop moves along an array, a counter climbs from 1 to n, a total grows as each new value is added. The method does the whole job itself, step by step, from beginning to end.
There is a second way of arranging a solution, and it is not obvious the first time you meet it. Instead of doing the whole job, the method does one small piece of it and then hands the rest of the job — which is the same kind of job, only smaller — back to itself.
Nothing about that idea depends on Java. It is a way of describing a problem, and it works only when the problem has a particular shape. This section is about recognising that shape, and about turning a description of it into a method.
11.1.1 Problems That Contain Smaller Copies of Themselves
Suppose a shopkeeper hands you a slip with eight prices written on it and asks for the total. You could add them one by one, which is what a loop would do. Or you could say something slightly odd but perfectly true: the total of the whole slip is the first price, plus the total of the remaining seven prices.
That second sentence has done almost no work. It has not added anything. What it has done is replace the original problem with a smaller problem of exactly the same kind — total a slip of seven prices — and the same sentence applies to that one too. Fig. 11.1-1 shows the reduction happening once.
Diagram
Fig. 11.1-1 – a horizontal strip divided into eight boxes holding prices; the leftmost box outlined heavily and labelled “first price”, the remaining seven boxes enclosed in a bracket labelled “a slip of seven prices - the same problem, one shorter”; below the strip the words “total of eight = first price + total of seven”
Keep applying it and the slip gets shorter each time: seven prices, six, five, and so on. Eventually you reach a slip with no prices on it at all, and there the answer needs no reasoning of any kind. The total of an empty slip is zero.
Two conditions, both needed
That last sentence is not a detail. It is half the method. A problem can be solved in this style only when two things are true at once.
The first condition is that the problem must reduce: a larger case must be expressible in terms of a strictly smaller case of the same problem. The second condition is that the shrinking must stop somewhere, at a case so small that its answer can be stated outright rather than worked out.
Miss the first condition and nothing gets smaller. Miss the second and the shrinking never ends. Both conditions have to hold, and in a moment you will see what each failure looks like in a running program.
This shape is more common than it looks. Folders on a computer hold files and other folders, so counting everything inside a folder means counting its files and then counting everything inside each folder it contains — the same task, on something smaller. A search through a sorted list can throw away half the list and search what is left. The rules of arithmetic themselves are full of it, as the next subsection shows.
11.1.2 Recursive Definitions in Mathematics
Mathematics used this idea long before there were computers to run it on. The factorial of a positive integer n, written \(n!\), is the product \(n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1\). That dotted line in the middle is doing a lot of quiet work, and it can be removed entirely.
Notice that \(5! = 5 \times 4 \times 3 \times 2 \times 1\), and that \(4 \times 3 \times 2 \times 1\) is just \(4!\). So \(5! = 5 \times 4!\), and the same relation holds for any n greater than zero. The factorial of a number is that number multiplied by the factorial of the number one below it. By convention \(0! = 1\), and that is the case that needs no working out.
Written out in full, the definition has two clauses and no dots at all:
\[0! = 1\] \[n! = n \times (n-1)! \quad \text{for } n > 0\]
A recursive definition is not circular, even though it appears to define factorial using factorial. It escapes circularity because the second clause always refers to a strictly smaller number, and the first clause catches that descent before it can go below zero.
Reading a definition backwards
The best way to convince yourself that such a definition works is to use it. Take \(4!\) and apply the second clause until the first clause becomes available:
4! = 4 x 3!
= 4 x (3 x 2!)
= 4 x (3 x (2 x 1!))
= 4 x (3 x (2 x (1 x 0!)))
= 4 x (3 x (2 x (1 x 1)))
= 4 x (3 x (2 x 1))
= 4 x (3 x 2)
= 4 x 6
= 24Read the working downwards and each line replaces one factorial with a smaller one. Read it upwards from the line where \(0!\) became 1, and each line turns a suspended multiplication into an actual number. Both directions matter, and section 11.2 shows that a running program does exactly this, in exactly this order.
Factorial is not a special case. The sum of the first n natural numbers can be defined the same way, as \(S(0) = 0\) and \(S(n) = n + S(n-1)\). So can a power: \(x^0 = 1\) and \(x^n = x \times x^{n-1}\) for \(n > 0\). In each pair, the first clause anchors the definition and the second clause takes one step down.
Now consider what happens if the anchoring clause is left out and only \(n! = n \times (n-1)!\) survives. Applying it to \(2!\) gives \(2 \times 1!\), then \(2 \times 1 \times 0!\), then \(2 \times 1 \times 1 \times (-1)!\), and there is nothing to stop it. The definition is not merely incomplete; it defines nothing at all, because the descent never reaches a value.
11.1.3 From a Recursive Definition to a Method
The reason recursive definitions matter to a programmer is that they translate into Java almost word for word. A two-clause definition becomes a method with an if for the clause that answers directly and an else for the clause that refers back to a smaller case.
A method that calls itself, directly or through another method, is called a recursive method. Fig. 11.1-2 sets the two clauses of the power definition beside the two branches of the method that implements it.
Diagram
Fig. 11.1-2 – a two-column correspondence figure; left column headed “Recursive definition” with two stacked boxes, upper box holding “x to the power 0 = 1” and lower box holding “x to the power n = x multiplied by x to the power (n-1)”; right column headed “Java method” with two stacked boxes, upper box holding “if (n == 0) return 1;” and lower box holding “else return x * power(x, n - 1);”; a horizontal arrow joining each left box to the box beside it, the upper arrow labelled “answered directly” and the lower arrow labelled “reduced by one step”
Before writing the method, state the problem as a specification and state the method of solution in words. That order matters more in this chapter than anywhere else in the book, because a recursive method is short enough to write down by imitation without understanding it, and it will then be wrong in ways that are hard to see.
The translation into Java is now mechanical.
The one part of that method worth staring at is return x * power(x, n - 1);. Java cannot carry out the multiplication until it knows what power(x, n - 1) comes to, so it suspends the multiplication, starts a fresh call, and comes back to finish the sum later. Section 11.2 follows that suspension in detail.
11.2 How a Recursive Method Runs
On paper, the two clauses of a recursive definition settle the answer between them. In a running program something more has to happen, because a method that has called itself has not finished, and the machine must remember everything the unfinished call was in the middle of doing.
This section opens up that mechanism. It uses the power() method of section 11.1.3, because a method you have already read is easier to follow than a new one, and traces what the machine does from the first call to the last returned value.
11.2.1 The Base Case and the Recursive Case
Every correct recursive method contains two kinds of branch, and they correspond exactly to the two kinds of clause in a recursive definition.
The branch that gives an answer without calling the method again is the base case. In power() it is if (n == 0) return 1;. The branch that produces the answer by calling the method again on a smaller problem is the recursive case, written in power() as return x * power(x, n - 1);.
The word “strictly” carries the weight. A recursive case that calls itself on a problem the same size as the one it was given is not a reduction at all, and the base case will never be reached however long the program runs.
So a recursive method is correct only when three things hold together: there is at least one base case; every recursive call moves the problem towards a base case; and the combination step correctly builds the larger answer out of the smaller one. Drop any of the three and the method fails, though each drop fails in a different way.
| Feature | Base case | Recursive case |
|---|---|---|
| Calls the method again | No | Yes, at least once |
| What it does | States the answer for the smallest case directly | Reduces the problem and combines the returned answer with the remaining work |
| Effect on the size of the problem | Ends the reduction | Makes the problem strictly smaller |
| Effect on the call stack | Allows the stack to start shrinking | Adds one more frame to the stack |
| If it is missing or wrong | The calls never stop; the program fails at run time | The answer returned is wrong, or the method never reaches the base case |
11.2.2 The Method Call Stack
To see why a self-calling method needs special support, look first at what happens on any ordinary method call.
When a method is invoked, the machine sets aside a small block of memory called a stack frame. The frame holds that call’s formal arguments, its local variables, and the address of the instruction to return to when the method finishes. When the method returns, its frame is discarded and control goes back to the saved address.
These frames are kept on the call stack, a region of memory that grows and shrinks at one end only. A new frame is added on top; the frame removed is always the topmost one. That discipline is called last in, first out (LIFO): the most recent call is the first to finish and be removed. You will meet the same discipline again as a data structure in its own right; here it is enough to know that the machine keeps the frames in this order.
Now the point. Each call gets its own frame, so each call has its own copy of x and n. When power(3, 4) calls power(3, 3), there are two frames on the stack, holding n equal to 4 and n equal to 3, and neither can disturb the other. Fig. 11.2-1 shows the stack at its deepest for the call power(3, 4).
Diagram
Fig. 11.2-1 – a vertical stack of five rectangular frames drawn one above the other, growing upwards; from the bottom the frames are labelled “power(x=3, n=4) - waiting”, “power(x=3, n=3) - waiting”, “power(x=3, n=2) - waiting”, “power(x=3, n=1) - waiting” and, at the top and shaded, “power(x=3, n=0) - base case, returns 1”; an arrow on the left pointing up labelled “frames added as calls are made”, an arrow on the right pointing down labelled “frames removed as calls return”; the bottom frame marked “called from main()”
The stack explains both the power and the cost of recursion. It is what allows five copies of the same method to be part-way through their work at the same time without confusing one another. It is also what a deep recursion consumes: five frames here, but a hundred thousand frames if the base case is a hundred thousand steps away.
11.2.3 Winding, Unwinding and the Returned Value
A recursive method therefore runs in two phases, and it is worth naming them, because most mistakes in reading recursive code come from thinking about only one of them.
In the winding phase the calls go outward. Each call reaches its recursive case, suspends the expression it was evaluating, and starts a fresh call. Nothing is multiplied, added or printed yet if the operation waits on a returned value; the work simply piles up.
In the unwinding phase the answers come back. The base case returns a value to the call below it; that call completes its suspended expression and returns a value to the call below that, and so on until the first call returns to main(). Fig. 11.2-2 shows both phases for power(3, 4).
Diagram
Fig. 11.2-2 – a V-shaped call chain; descending down the left arm, five labelled boxes “power(3,4)”, “power(3,3)”, “power(3,2)”, “power(3,1)”, “power(3,0)” joined by downward arrows marked “calls”; ascending up the right arm, upward arrows marked with the returned values 1, then 3, then 9, then 27, then 81, each arrow drawn from a box to the box above it; the left arm labelled “winding: calls made, work suspended” and the right arm labelled “unwinding: values returned, work completed”
| Step | Call in progress | n |
What happens | Value returned |
|---|---|---|---|---|
| 1 | power(3, 4) |
4 | n is not 0; suspends 3 * ? and calls power(3, 3) |
— |
| 2 | power(3, 3) |
3 | n is not 0; suspends 3 * ? and calls power(3, 2) |
— |
| 3 | power(3, 2) |
2 | n is not 0; suspends 3 * ? and calls power(3, 1) |
— |
| 4 | power(3, 1) |
1 | n is not 0; suspends 3 * ? and calls power(3, 0) |
— |
| 5 | power(3, 0) |
0 | base case reached; returns at once | 1 |
| 6 | power(3, 1) |
1 | completes 3 * 1 |
3 |
| 7 | power(3, 2) |
2 | completes 3 * 3 |
9 |
| 8 | power(3, 3) |
3 | completes 3 * 9 |
27 |
| 9 | power(3, 4) |
4 | completes 3 * 27; returns to the caller |
81 |
Result: the call power(3, 4) returns 81, which is \(3^4\). The trace shows that four of the five calls do no multiplication at all until the base case has returned, and that the multiplications then happen in the reverse of the order in which they were set up.
That reversal is the single most useful thing to remember when reading recursive code. The calls run outward in the order you read them; the suspended work completes inward, in the opposite order.
11.2.4 Recursion Without a Base Case
Section 11.1.2 showed a factorial definition with its anchoring clause removed, and observed that it defines nothing. A program in the same condition does something more visible: it fails.
A recursive method whose calls never reach a base case is said to perform infinite recursion. The calls do not run forever, though. Each one adds a frame to the call stack, the stack has a finite size, and when there is no room for another frame the Java Virtual Machine stops the program and reports a StackOverflowError. On most machines this happens after some thousands of calls, so the failure arrives quickly.
There are two distinct ways to fall into it, and they look quite different in the code.
The first is the obvious one: no base case at all. The method has a recursive case and nothing else, so there is no branch that could ever return without calling again.
The second is more common and much harder to spot: the base case is present and correct, but the recursive call does not move towards it. The method reduces nothing, so the same case is met again and again.
It is worth being clear about why this matters beyond a crashed program. A method that consumes memory without limit is not a small stylistic flaw; it is a correctness failure, and the habit of checking that every recursion is bounded before running it is part of writing dependable code.
11.3 Simple Recursive Methods on Numbers
The pattern is now fixed: find a reduction, find a case that needs no reduction, write one branch for each. This section applies it to three problems on whole numbers. They are worth doing carefully rather than quickly, because the third one reduces in a way the first two do not, and that difference matters more than it first appears.
11.3.1 Factorial of a Number
Section 11.1.2 gave the recursive definition of factorial: \(0! = 1\), and \(n! = n \times (n-1)!\) for \(n > 0\). The base case is the first clause, the recursive case is the second, and the argument falls by exactly one at every call.
11.3.2 Sum of the First n Natural Numbers
The sum \(1 + 2 + 3 + \cdots + n\) has the same shape as factorial with the multiplication replaced by addition. The sum of the first n natural numbers is n added to the sum of the first n-1 of them, and the sum of the first zero of them is 0.
\[S(0) = 0\] \[S(n) = n + S(n-1) \quad \text{for } n > 0\]
The method follows the definition directly:
int sum(int n)
{
if (n == 0)
{
return 0;
}
else
{
return n + sum(n - 1);
}
}This method is correct, and it is also a good example of recursion being the wrong tool. There is a closed form for this sum, \(S(n) = \frac{n(n+1)}{2}\), which any calculator settles in one step. For n equal to 1000 the recursive method makes 1001 calls and stacks 1001 frames; the formula performs one multiplication, one addition and one division.
That comparison is worth holding on to. Recursion is a way of organising a solution, not evidence that the solution is a good one. When a direct formula exists, it wins on both time and memory, and the recursive version earns its place only as a way of understanding the structure of the sum.
11.3.3 Greatest Common Divisor of Two Numbers
The greatest common divisor (GCD) of two whole numbers, not both zero, is the largest number that divides both of them exactly. The GCD of 48 and 18 is 6, because 6 divides both and no larger number does.
You could find it by testing every number downwards from the smaller of the two, but there is a far better reduction, and it is the oldest algorithm still in regular use. It rests on one observation: any number that divides both a and b also divides the remainder left when a is divided by b. So the pair (a, b) and the pair (b, a mod b) have exactly the same set of common divisors, and therefore the same greatest common divisor.
That gives the reduction. The base case arrives when the second number becomes 0, because every number divides 0 exactly, and so the GCD of a and 0 is a.
Fig. 11.3-1 shows the pairs the method passes through.
Diagram
Fig. 11.3-1 – a horizontal chain of four boxes joined by right-pointing arrows; the boxes hold the pairs “(48, 18)”, “(18, 12)”, “(12, 6)” and “(6, 0)”; each arrow labelled with the remainder computed at that step, reading “48 mod 18 = 12”, “18 mod 12 = 6” and “12 mod 6 = 0”; the last box shaded and labelled “base case: answer is 6”
| Step | Call in progress | a |
b |
What happens | Value returned |
|---|---|---|---|---|---|
| 1 | gcd(48, 18) |
48 | 18 | b is not 0; computes 48 % 18 = 12 and calls gcd(18, 12) |
— |
| 2 | gcd(18, 12) |
18 | 12 | b is not 0; computes 18 % 12 = 6 and calls gcd(12, 6) |
— |
| 3 | gcd(12, 6) |
12 | 6 | b is not 0; computes 12 % 6 = 0 and calls gcd(6, 0) |
— |
| 4 | gcd(6, 0) |
6 | 0 | base case reached; returns a |
6 |
| 5 | gcd(12, 6) |
12 | 6 | passes back what it received | 6 |
| 6 | gcd(18, 12) |
18 | 12 | passes back what it received | 6 |
| 7 | gcd(48, 18) |
48 | 18 | passes back what it received | 6 |
Result: the call gcd(48, 18) returns 6. The trace shows something the factorial trace did not: on the way back, no call does any work at all. Each one simply returns what the call above it returned, because the whole answer was already known at the base case.
Notice also how fast the descent is. Factorial goes 5, 4, 3, 2, 1, 0 — one step at a time. This method goes 48, 18, 12, 6, 0 in four steps. A reduction that divides is worth far more than a reduction that subtracts one, and the same difference appears again in section 11.5 when a search throws away half a list at every call.
There is an older version of the same idea that replaces the larger number by the difference of the two, repeating until they are equal. It is correct, and for 48 and 18 it works quickly enough. But for the pair 1000000 and 3 it needs hundreds of thousands of steps, where the remainder version needs two. Both are reductions; only one of them is a good reduction.
11.4 Recursion on the Digits of a Number
The problems in section 11.3 reduced a number by counting it down or by taking a remainder. There is a third reduction, and it is the one behind a large family of programs: strip a number of its last digit and deal with what is left.
Two operations from Class XI do all the work here, and they are worth restating because everything in this section depends on them. For a positive integer stored in an int, the expression n % 10 gives its last digit, and n / 10 gives the number that remains when that digit is removed, because division of one int by another discards the fractional part. For 4072 these give 2 and 407.
That is a reduction: 4072 becomes 407, which becomes 40, then 4, then 0. It is guaranteed to reach 0, since dividing a positive number by 10 always makes it strictly smaller. Fig. 11.4-1 shows the peeling.
Diagram
Fig. 11.4-1 – a vertical sequence of five rows; each row shows the current value in a box on the left, an arrow to the right labelled “n % 10” pointing to the digit removed, and an arrow downwards labelled “n / 10” pointing to the next box; the boxes read 4072, 407, 40, 4, 0 from top to bottom, and the digits removed alongside them read 2, 7, 0, 4; the last box shaded and labelled “base case: nothing left”
11.4.1 Extracting Digits Recursively
Adding up the digits of a number is the simplest use of this reduction. The sum of the digits of a number is its last digit plus the sum of the digits of what remains, and the sum of the digits of 0 is 0.
The order in which digits appear
Addition does not care about order, so the sum comes out right whichever way round the digits are taken. Printing does care, and here recursion has a property worth understanding properly.
Consider a method that prints the digits one by one, and look at where the printing statement sits relative to the recursive call.
void showDigits(int n)
{
if (n > 0)
{
System.out.print(n % 10 + " ");
showDigits(n / 10);
}
}For an argument of 4072 this prints:
2 7 0 4Each call prints before it hands on, so the digits appear in the order they are stripped off — last digit first. Now move the printing statement to the other side of the call.
void showDigits(int n)
{
if (n > 0)
{
showDigits(n / 10);
System.out.print(n % 10 + " ");
}
}For the same argument this prints:
4 0 7 2Nothing else changed. The second version prints during the unwinding phase described in section 11.2.3, when the calls complete in the reverse of the order in which they were made. So the digits come out in the reverse of the order they were stripped off, which is the order they are written in.
| Feature | Work before the call | Work after the call |
|---|---|---|
| Phase in which it happens | Winding, as the calls go outward | Unwinding, as the calls return |
| Order of the results | The same order as the reduction | The reverse of the order of the reduction |
| For the digits of 4072 | 2 7 0 4 | 4 0 7 2 |
| Typical use | Handling an item as soon as it is reached | Producing reversed output without storing anything |
11.4.2 Converting a Number Between Bases
Everything so far has assumed 10 as the base. Nothing in the reduction requires it. Dividing by 2 instead of 10 and keeping the remainders gives the binary representation of a number; dividing by 8 gives the octal representation.
The familiar hand method is to divide repeatedly by the base, note each remainder, and then read the remainders upwards, from the last obtained to the first. That closing instruction — read them backwards — is exactly what a recursive method gives for nothing, as the previous subsection showed.
So the representation of n in base b is the representation of n / b in base b, followed by the digit n % b. And when n is already smaller than b it is a single digit, and is its own representation.
Fig. 11.4-2 follows the conversion of 45 into base 2.
Diagram
Fig. 11.4-2 – two parallel columns; the left column, headed “calls going down”, holds boxes convert(45,2), convert(22,2), convert(11,2), convert(5,2), convert(2,2), convert(1,2) joined by downward arrows; the right column, headed “strings coming back”, holds boxes “1”, “10”, “101”, “1011”, “10110”, “101101” joined by upward arrows, each aligned with the call that returns it; the lowest left box shaded and labelled “1 is less than 2: base case”; between the columns the remainder appended at each level is shown, reading upwards, as 0, 1, 1, 0, 1
| Step | Call in progress | n |
n / b |
n % b |
Value returned |
|---|---|---|---|---|---|
| 1 | convert(45, 2) |
45 | 22 | 1 | suspended |
| 2 | convert(22, 2) |
22 | 11 | 0 | suspended |
| 3 | convert(11, 2) |
11 | 5 | 1 | suspended |
| 4 | convert(5, 2) |
5 | 2 | 1 | suspended |
| 5 | convert(2, 2) |
2 | 1 | 0 | suspended |
| 6 | convert(1, 2) |
1 | — | — | "1" |
| 7 | convert(2, 2) |
2 | 1 | 0 | "10" |
| 8 | convert(5, 2) |
5 | 2 | 1 | "101" |
| 9 | convert(11, 2) |
11 | 5 | 1 | "1011" |
| 10 | convert(22, 2) |
22 | 11 | 0 | "10110" |
| 11 | convert(45, 2) |
45 | 22 | 1 | "101101" |
Result: the call returns "101101", and \(1 \times 32 + 0 \times 16 + 1 \times 8 + 1 \times 4 + 0 \times 2 + 1 \times 1 = 45\) confirms it. The trace shows the answer growing from its leftmost digit outwards, which is why the method contains no reversal step anywhere.
11.5 Recursion on Arrays and Strings
A number reduces by division or by losing a digit. An array or a string reduces in a different way: the data stays where it is, and what shrinks is the part of it still under consideration. Nothing is removed and, if the method is written well, nothing is copied either. Each call simply works on a narrower stretch than the call that made it.
That change of viewpoint is the whole of this section. Once you can describe a portion of an array by the two positions that fence it in, recursion on arrays becomes as ordinary as recursion on numbers.
11.5.1 Binary Search on a Sorted Array
Searching a sorted list of ten thousand values one element at a time is wasteful, and you already know why from looking up a name in a printed directory. Nobody starts at the first page. You open somewhere near the middle, see which half the name must lie in, and forget the other half completely.
Binary search is that method written down precisely. It applies only to data arranged in order, and it works by repeatedly discarding half of what is left.
Compare the value being looked for with the element in the middle of the current stretch. If they are equal, the search is over. If the value is smaller, it cannot lie in the middle element or anything after it, so the search continues in the stretch before the middle. If it is larger, the search continues in the stretch after the middle. Each of those continuations is the same problem on a shorter stretch, which is exactly the shape recursion wants.
A stretch is described by two positions, low and high. The search stops in one of two ways: the value is found at the middle position, or the stretch becomes empty, which happens when low passes high. Both are base cases, and a method without the second could never report failure.
Fig. 11.5-1 follows a search for 78 in a list of ten sorted marks.
Diagram
Fig. 11.5-1 – four horizontal rows, each showing the same ten-cell array holding 12, 25, 31, 44, 57, 63, 78, 89, 91, 96 with indices 0 to 9 printed beneath the cells; in row one the whole array is live, the cell at index 4 is ringed and labelled “middle: 57 is too small”, and cells 0 to 4 are then greyed; in row two cells 5 to 9 are live, the cell at index 7 is ringed and labelled “middle: 89 is too large”, and cells 7 to 9 are then greyed; in row three cells 5 and 6 are live, the cell at index 5 is ringed and labelled “middle: 63 is too small”; in row four only cell 6 is live, ringed and labelled “middle: 78 found at index 6”
| Step | Call in progress | low |
high |
mid |
a[mid] |
What happens | Value returned |
|---|---|---|---|---|---|---|---|
| 1 | search(a, 0, 9, 78) |
0 | 9 | 4 | 57 | 78 is greater; searches 5 to 9 | suspended |
| 2 | search(a, 5, 9, 78) |
5 | 9 | 7 | 89 | 78 is smaller; searches 5 to 6 | suspended |
| 3 | search(a, 5, 6, 78) |
5 | 6 | 5 | 63 | 78 is greater; searches 6 to 6 | suspended |
| 4 | search(a, 6, 6, 78) |
6 | 6 | 6 | 78 | equal; base case reached | 6 |
| 5 | search(a, 5, 6, 78) |
5 | 6 | 5 | 63 | passes back what it received | 6 |
| 6 | search(a, 5, 9, 78) |
5 | 9 | 7 | 89 | passes back what it received | 6 |
| 7 | search(a, 0, 9, 78) |
0 | 9 | 4 | 57 | passes the answer back to main() |
6 |
Result: the value is found at index 6 after examining four of the ten elements. As in the greatest common divisor trace of section 11.3.3, the unwinding does no work at all — the answer was complete the moment the base case was reached.
11.5.2 Working Through a String Recursively
A String in Java is an object holding a sequence of characters, and three of its methods cover almost all recursion on strings: length() gives the number of characters, charAt() gives the character at a stated position counting from 0, and substring() gives a piece of the string.
The obvious reduction is to peel one character off the front. A string is its first character followed by the rest of it, and s.substring(1) is that rest — the whole string with the first character removed. The base case is the empty string, whose length is 0.
Reversing a string follows directly. The reverse of a string is the reverse of everything after its first character, with that first character joined on at the end.
String reverse(String s)
{
if (s.length() == 0)
{
return "";
}
else
{
return reverse(s.substring(1)) + s.charAt(0);
}
}Given "abc", the calls descend to the empty string and the answer builds back up as "c", then "cb", then "cba".
This is correct, and it carries a cost worth knowing about. substring() does not shorten the existing string; it produces a new one. A recursion of this shape on a string of 500 characters therefore creates 500 new string objects. At the lengths a school program deals with that hardly matters, but the technique of section 11.5.1 — leaving the data alone and moving two positions instead — avoids it altogether, and works just as well on strings.
A reduction from both ends
Checking whether a word reads the same forwards and backwards needs no reversal at all. Compare the first character with the last. If they differ, the answer is no and nothing else need be looked at. If they match, the question reduces to the same question about everything between them.
There are two base cases here and they are easy to miss. A stretch of one character reads the same both ways, and so does an empty stretch, which is what a word of even length reduces to. The single test left >= right covers both. Fig. 11.5-2 shows the two positions closing in.
Diagram
Fig. 11.5-2 – three stacked rows, each showing the nine letters of the word MALAYALAM in separate cells with indices 0 to 8 beneath; in row one, arrows from outside point at index 0 and index 8, both cells shaded, labelled “M and M match”; in row two, arrows point at index 1 and index 7, both shaded, labelled “A and A match”; in row three, a single arrow points at index 4, shaded, labelled “left has reached right: base case, answer is true”; cells already checked are greyed in each later row
11.6 Forms of Recursion
Every method in this chapter so far has called itself, once, from one place in its own body. That is the commonest arrangement but not the only one. A method can call itself from two places; it can call itself twice in a single expression; and it can avoid calling itself at all while still being recursive, by calling a second method that calls the first one back.
These arrangements are given names, and the names are worth knowing for a practical reason: they predict how the method will behave. One form can be turned into a loop with almost no thought. Another can make a ten-line method take longer than you are prepared to wait.
11.6.1 Direct Recursion
When a method contains a call to itself inside its own body, the arrangement is called direct recursion. Everything written so far in this chapter is of this kind: power(), factorial(), gcd(), sumOfDigits(), convert(), search() and reverse() all name themselves in their own code.
Direct recursion is classified further by how many recursive calls a single invocation actually makes, and by where the call sits in relation to the rest of the work. Those two questions give the next two subsections.
11.6.2 Tail Recursion
Compare two lines you have already read closely. In factorial() the recursive case is return n * factorial(n - 1); and in gcd() it is return gcd(b, a % b);.
The difference is small on the page and large in the machine. In factorial(), when the recursive call returns, there is still a multiplication to perform — the call is not the last thing that happens. In gcd() there is nothing left to do at all; whatever the call returns is what this invocation returns.
A recursive method in which the recursive call is the last action performed is said to use tail recursion.
The dry run of gcd() in section 11.3.3 showed exactly what this looks like from the inside: on the way back, three of the four calls did nothing at all except hand on the value they had received. That is the signature of tail recursion. Nothing is suspended, so the unwinding phase carries no work.
This matters because a tail-recursive method can be rewritten as a loop almost mechanically. The arguments of the next call become new values assigned to the same variables, and the base-case test becomes the loop condition:
int gcd(int a, int b)
{
while (b != 0)
{
int r = a % b;
a = b;
b = r;
}
return a;
}This loop performs the same divisions in the same order and returns the same answer, using two variables and no stack frames beyond the one call. Try the same rewriting on factorial() and you will find it needs an extra variable to hold the growing product, because the suspended multiplications have to be kept somewhere.
One honest correction is needed here, because it is often stated the other way round. Factorial is not an example of tail recursion. Its recursive call is followed by a multiplication, so work does remain after the call returns. Greatest common divisor is a genuine example; so is the binary search of section 11.5.1, where the value returned by the inner call is passed straight back.
11.6.3 Binary Recursion
When a single invocation of a method makes two recursive calls, the arrangement is called binary recursion. The two calls may be written in one expression or in two separate statements; what matters is that both of them run.
The standard example is the Fibonacci sequence. It begins 0, 1, 1, 2, 3, 5, 8, 13, and each term after the first two is the sum of the two before it. Numbering the terms from zero, the definition is:
\[F(0) = 0, \quad F(1) = 1\] \[F(n) = F(n-1) + F(n-2) \quad \text{for } n > 1\]
There are two base cases, because the recursive clause reaches two terms back and so needs two anchored terms rather than one.
Now look at what this method costs, because it is startling. Fig. 11.6-1 draws every call made by fib(5).
Diagram
Fig. 11.6-1 – a recursion tree with root node labelled “fib(5)” at the top; the root has two children joined by downward edges, the left edge labelled “n - 1” leading to “fib(4)” and the right edge labelled “n - 2” leading to “fib(3)”; “fib(4)” has children “fib(3)” and “fib(2)”; the right-hand “fib(3)” has children “fib(2)” and “fib(1)”; the left-hand “fib(3)” has children “fib(2)” and “fib(1)”; every “fib(2)” node has children “fib(1)” and “fib(0)”; all “fib(1)” and “fib(0)” nodes drawn shaded and labelled “base case”; a caption beneath reading “15 calls in all to obtain the value 5; the subtree for fib(3) is computed twice and fib(2) three times”
Fifteen calls to produce the number 5. The reason is visible in the tree: the subtree for fib(3) appears twice, and everything inside it is computed twice over. Nothing is remembered between the two branches, so the same work is repeated.
The effect compounds. The tenth term needs 177 calls; the thirtieth term needs about 2.7 million; and each further step upward roughly doubles the total again. An iterative version that keeps the last two terms in two variables computes the thirtieth term in twenty-nine additions.
That repetition can be avoided, but the techniques for doing so belong to later study. What matters here is the diagnosis: two recursive calls per invocation means a tree of calls, and a tree of calls grows fast.
Two call sites are not the same as two calls
Binary search, in section 11.5.1, contains two recursive calls in its text — one in the else if branch and one in the else branch. It is not binary recursion, because only one of the two ever runs on any given invocation. The other is not merely unused; it is not reached at all. Its calls form a chain of about \(\log_2 n\) links, not a tree.
So when classifying a method, count the calls that a single invocation actually makes, not the calls you can see in the code.
11.6.4 Indirect Recursion
A method can be recursive without ever naming itself. If method A calls method B, and B calls A, then a call to A eventually leads back to A. This is indirect recursion, also called mutual recursion, and Fig. 11.6-2 shows the shape of it.
Diagram
Fig. 11.6-2 – two rounded boxes side by side, the left labelled “isEven(n)” and the right labelled “isOdd(n)”; a curved arrow from the left box to the right box labelled “calls isOdd(n - 1)” and a second curved arrow from the right box back to the left box labelled “calls isEven(n - 1)”; each box carries a small tag beneath it, the left reading “base case: n is 0, answer true” and the right reading “base case: n is 0, answer false”
The example below decides whether a number is even. A number is even if the number one below it is odd, and it is odd if the number one below it is even. Zero is even, and zero is not odd — those two facts are the base cases, and at least one of them must be reachable or the pair of methods would never stop.
| Feature | Tail recursion | Binary recursion | Indirect recursion |
|---|---|---|---|
| Where the call appears | In the method’s own body, as its last action | In the method’s own body, twice per invocation | In a second method that calls the first one back |
| Calls made per invocation | One | Two | One, but to a different method |
| Shape of the calls | A chain | A tree | A cycle between two or more methods |
| Work left after the call returns | None | The two returned values must be combined | Depends on the method |
| Converts to a loop easily | Yes | No | No |
| Example in this chapter | gcd() |
fib() |
isEven() and isOdd() |
11.7 Recursion Compared With Iteration
Both a loop and a recursive method make something happen many times, and for many problems either will produce the correct answer. The choice between them is therefore not about what is possible but about what things cost and what reads clearly, and those two considerations do not always point the same way.
Iteration is repetition by means of a loop: a for, while or do while statement returns control to the top of a block until a condition fails. Recursion is repetition by means of calls: the method restarts itself on a smaller problem. This section puts the two side by side honestly, including in the places where recursion loses.
11.7.1 What Each Repetition Actually Costs
Take the sum of the first n natural numbers, whose recursive method appeared in section 11.3.2. The iterative version is this:
int sum(int n)
{
int total = 0;
for (int i = 1; i <= n; i++)
{
total = total + i;
}
return total;
}Both versions perform n additions. That is where the similarity ends.
Each repetition of the loop costs a comparison, an addition, an increment and a jump back to the top of the block. The two variables total and i are created once and reused, and the method occupies one stack frame from beginning to end however large n is.
Each repetition of the recursive version costs all the arithmetic the loop does, and then the machinery of a method call as well: a new stack frame is set aside, the argument is copied into it, the return address is saved, and on the way back the frame is discarded and the suspended addition completed. None of that work contributes to the answer. It is the price of arranging the repetition as calls.
Fig. 11.7-1 shows what this means for memory.
Diagram
Fig. 11.7-1 – a two-panel comparison for computing the sum of the first five natural numbers; left panel headed “Iteration” showing a single rectangular frame labelled “sum(5)” containing two variable boxes “total” and “i”, with a note beneath reading “one frame, whatever n is; the two variables take new values on each pass”; right panel headed “Recursion” showing six stacked frames labelled from bottom to top “sum(5)”, “sum(4)”, “sum(3)”, “sum(2)”, “sum(1)”, “sum(0)”, the topmost shaded and marked “base case”, with a note beneath reading “n + 1 frames, all held at the same time”
11.7.2 Choosing Between the Two
The comparison below gathers what the chapter has established. Read it as a set of tendencies, not as a rule that decides every case on its own.
| Feature | Recursion | Iteration |
|---|---|---|
| How the repetition is produced | The method calls itself on a smaller problem | A loop returns control to the top of a block |
| What stops it | A base case that returns without calling again | A loop condition that becomes false |
| Memory used | One stack frame per level of depth | A fixed amount, independent of the number of passes |
| Cost per repetition | The work itself, plus the cost of a call and a return | The work itself, plus a test and an update |
| Risk when the input is large | StackOverflowError once the stack is full |
None from repetition alone |
| Where it reads better | Problems whose definition is itself recursive, or whose structure branches | Problems that sweep once through a range or a collection |
| Typical failure when written wrongly | The base case is never reached and the program stops at run time | The loop condition never becomes false and the program hangs |
Two practical guidelines follow from the table.
Prefer recursion when the problem is defined in terms of a smaller version of itself and the depth of the recursion stays modest. Converting a number to another base, searching a sorted array, and any problem whose structure branches into sub-problems fall into this group. The method then reads almost exactly like the definition it implements, and a short method that mirrors its specification is easier to check for correctness than a longer one that does not.
Prefer iteration when the repetition is a straightforward sweep — totalling an array, printing a table of values, reading a fixed number of inputs — or when the number of repetitions could be large. Nothing is gained by making a sweep recursive, and a great deal of memory is spent on it.
There is also a third possibility, and it is easy to forget in a chapter about recursion. Sometimes neither is needed. The sum of the first n natural numbers has the closed form \(\frac{n(n+1)}{2}\), which finishes in one step and makes both versions of sum() unnecessary. Before choosing how to repeat something, it is worth asking whether it needs repeating at all.
The next section takes a problem where the choice is not close. It has no formula, no simple sweep, and an iterative solution that is genuinely difficult to write — and a recursive solution of three lines.
11.8 The Tower of Hanoi
Every recursive method in this chapter has had an obvious iterative rival. Factorial, digit sums, base conversion, binary search and string reversal can all be written with a loop, and for some of them the loop is the better choice.
This section takes a problem where that is not so. Its recursive solution is three lines long and can be checked by reasoning; its iterative solution exists but is genuinely awkward to construct. It is the example the syllabus itself singles out.
11.8.1 The Puzzle and Its Rules
The Tower of Hanoi uses three vertical pegs and a set of discs, all of different sizes. At the start every disc is on the first peg, arranged in order of size with the largest at the bottom, as in Fig. 11.8-1. The task is to move the whole pile to the third peg.
Diagram
Fig. 11.8-1 – three vertical pegs standing on a horizontal base, labelled A, B and C from left to right; peg A carries three discs stacked in order of size, the widest at the bottom and the narrowest at the top, each labelled with its number, disc 3 at the bottom, disc 2 in the middle and disc 1 on top; pegs B and C are empty; a caption reading “start: all discs on A; goal: all discs on C, in the same order”
Three rules govern every move:
- Only one disc may be moved at a time.
- Only the topmost disc of a peg may be moved, and it must be placed on top of another peg.
- A disc may never be placed on top of a smaller disc.
The third rule is the whole difficulty. Without it the puzzle would be a matter of lifting discs across one by one. With it, every large disc that has to move must first have everything above it taken somewhere else — and that somewhere else must itself be a legal arrangement.
11.8.2 The Recursive Solution
Trying to plan the moves from the beginning is hopeless, and it is the wrong way to think about the problem. Think instead about the largest disc.
The largest disc has to get from peg A to peg C at some point. For that single move to be legal, two conditions must hold: nothing may be sitting on top of it, and peg C must be empty. So immediately before it moves, all the other discs must be stacked on the remaining peg, peg B.
That observation does the whole job, because it converts the problem into a smaller problem of exactly the same kind. Moving n discs from a source peg to a target peg breaks into three steps, shown in Fig. 11.8-2.
Diagram
Fig. 11.8-2 – three panels in a row, each showing three pegs labelled A, B and C on a base; panel 1 headed “Step 1” shows a stack of two smaller discs having moved from A to B with A holding only the largest disc, captioned “move the top n-1 discs from A to B, using C as the spare peg”; panel 2 headed “Step 2” shows the largest disc moved from A to C with the two smaller discs still on B, captioned “move the largest disc from A to C”; panel 3 headed “Step 3” shows all discs stacked in order on C, captioned “move the n-1 discs from B to C, using A as the spare peg”
Steps 1 and 3 are the same puzzle with one disc fewer, so the method calls itself for them. Step 2 is a single move and needs no thought. The base case is a pile of one disc, which simply moves from its peg to the target.
Two points make the solution correct, and both are worth stating because they are what a student is usually asked to explain.
First, the recursive calls are always legal. While steps 1 and 3 are being carried out, the largest disc is either at the bottom of the source peg or already resting on the target peg. Either way it is larger than every disc being moved, so no rule is broken by placing any of them on it. In effect the largest disc can be ignored during those steps.
Second, the reduction always terminates. Each call passes n-1 where it received n, so the sequence of sizes falls by one each time and must reach 1.
Note carefully what changes in the arguments of the two recursive calls. In step 2 the target peg becomes the spare; in step 4 the source peg becomes the spare. Getting those exchanges right is the only fiddly part of writing the method.
| Step | Call | n |
from |
spare |
to |
Line printed |
|---|---|---|---|---|---|---|
| 1 | shift(3, A, B, C) |
3 | A | B | C | — (first calls shift(2, A, C, B)) |
| 2 | shift(2, A, C, B) |
2 | A | C | B | — (first calls shift(1, A, B, C)) |
| 3 | shift(1, A, B, C) |
1 | A | B | C | Move disc 1 from A to C |
| 4 | shift(2, A, C, B) |
2 | A | C | B | Move disc 2 from A to B |
| 5 | shift(1, C, A, B) |
1 | C | A | B | Move disc 1 from C to B |
| 6 | shift(3, A, B, C) |
3 | A | B | C | Move disc 3 from A to C |
| 7 | shift(2, B, A, C) |
2 | B | A | C | — (first calls shift(1, B, C, A)) |
| 8 | shift(1, B, C, A) |
1 | B | C | A | Move disc 1 from B to A |
| 9 | shift(2, B, A, C) |
2 | B | A | C | Move disc 2 from B to C |
| 10 | shift(1, A, B, C) |
1 | A | B | C | Move disc 1 from A to C |
Result: seven lines are printed, in the order shown in the sample output. The trace makes the structure visible — the first three printed lines transfer two discs to peg B, the fourth moves the largest disc, and the last three transfer the same two discs onto peg C.
11.8.3 Counting the Moves
The three steps of the method also count the moves for us. Moving n discs costs whatever it takes to move n-1 discs, plus one move for the largest disc, plus the cost of moving n-1 discs again. Writing \(M(n)\) for the number of moves:
\[M(1) = 1\] \[M(n) = 2 \times M(n-1) + 1 \quad \text{for } n > 1\]
Work the values upward and the pattern appears at once: 1, 3, 7, 15, 31, 63. Each is one less than a power of two, and the general result is \(M(n) = 2^n - 1\).
| Number of discs | Number of moves, \(2^n - 1\) |
|---|---|
| 3 | 7 |
| 4 | 15 |
| 5 | 31 |
| 10 | 1023 |
| 20 | 1048575 |
| 64 | 18446744073709551615 |
No shorter solution exists, and the reason is the same observation the method was built on. The largest disc must move at least once, and it cannot move until the other n-1 discs are all stacked on the single remaining peg — which is itself a full transfer of n-1 discs. A second full transfer of n-1 discs is then needed to bring them onto the target. So at least \(2 \times M(n-1) + 1\) moves are unavoidable, which is exactly what the method uses.
The last row of the table settles the temple story. At one move every second, without pause or error, sixty-four discs would take something over eighteen quintillion seconds, which is roughly 585 billion years.
One last observation ties this section to section 11.6.3. The method makes two recursive calls per invocation, so its calls form a tree, and the number of moves grows exponentially. But the depth of that tree is only n, so a puzzle of twenty discs needs just twenty stack frames while producing over a million lines of output. A tree of calls can be enormous and shallow at the same time, and it is the depth, not the total, that the call stack has to hold.
11.9 Summary
The idea
- Recursion is the technique of solving a problem by expressing its solution in terms of the solution to a smaller case of the same problem, together with at least one smallest case whose solution is stated directly.
- A problem can be solved this way only when two conditions hold together: a larger case must reduce to a strictly smaller case of the same problem, and the reduction must reach a case that is answered outright.
- A recursive definition has two kinds of clause — one that gives the answer for the smallest case, and one that gives the answer for a larger case in terms of a smaller one. Such a definition is not circular, because the second clause always refers to a strictly smaller value.
- Recursive definitions translate into Java almost word for word: the clause that answers directly becomes the
ifbranch, and the clause that refers back becomes theelsebranch.
Base case and recursive case
- The base case is the case for which the method returns an answer without calling itself again. The recursive case obtains its answer by calling the method on a strictly smaller problem and combining the returned value with the work that remains.
- A recursive method is correct only when all three of the following hold: at least one base case exists; every recursive call moves the problem towards a base case; and the combining step correctly builds the larger answer from the smaller one.
- A wrong base case does not usually crash the method. It returns a wrong answer quietly, shifted by a constant amount.
- Infinite recursion occurs when the calls never reach a base case, either because none exists or because the argument passed on is not smaller. The stack fills and the program stops at run time with a
StackOverflowError.
What happens when a recursive method runs
- Every method call is given a stack frame holding its formal arguments, its local variables and the address to return to. Frames are kept on the call stack in last in, first out order, so the most recent call is the first to finish.
- Each call has its own copies of the arguments and locals, which is why several calls to the same method can be part-way through their work at once without interfering.
- A recursive method runs in two phases. In the winding phase the calls go outward and work is suspended; in the unwinding phase the values are returned and the suspended work is completed, in the reverse of the order in which it was set up.
Reductions used in this chapter
- Subtract one: factorial, defined as \(0! = 1\) and \(n! = n \times (n-1)!\) for \(n > 0\); the sum of the first n natural numbers, defined as \(S(0) = 0\) and \(S(n) = n + S(n-1)\); and a whole-number power, defined as \(x^0 = 1\) and \(x^n = x \times x^{n-1}\). Each makes \(O(n)\) calls and stacks \(O(n)\) frames, where n is the argument.
- Replace by a remainder: the greatest common divisor, defined as the GCD of a and 0 being a, and the GCD of a and b being the GCD of b and a mod b. It works because the pair (a, b) and the pair (b, a mod b) have the same common divisors, and it reaches an answer in far fewer calls than a reduction by one.
- Strip a digit:
n % 10gives the last digit andn / 10removes it, so digit problems take one call per digit. - Divide by the base: to convert a number to base b, the representation of n divided by b is obtained first and the remainder of n divided by b is attached to its right-hand end. Recursion supplies the reversal of the remainders for nothing; attaching the remainder before the recursive call produces the digits in reverse order.
- Halve the range: binary search compares the key with the middle element and searches only one half, giving \(O(\log n)\) comparisons in the worst case and \(O(1)\) in the best case, where n is the number of elements. It has two base cases — the key found at the middle, and an empty range signalled by
lowpassinghigh. It requires the array to be sorted; on unsorted data it is not slow but wrong. - Peel a character: a string reduces either by
substring(1), which creates a new string at every call, or by moving an index along, which creates none.
Limitations to keep in view
- The depth of a recursion is the number of frames held at once, so the size of the input is limited by the size of the stack.
- Values can overflow their type long before recursion becomes a problem: an
intholds factorials only up to \(12!\), after which the multiplication wraps round and produces a meaningless answer without any warning. - A problem being solvable recursively is not a reason to solve it that way. Where a closed form exists, such as \(\frac{n(n+1)}{2}\) for the sum of the first n natural numbers, it settles the answer in one step.
Forms of recursion
- Direct recursion: a method contains a call to itself in its own body.
- Tail recursion: the recursive call is the last action the method performs, so nothing is left to do when it returns. Such methods convert to loops almost mechanically. The greatest common divisor method and binary search are tail recursive; factorial is not, because a multiplication follows its call. Java does not reuse the frame of a tail call, so the memory saving is not automatic.
- Binary recursion: one invocation makes two recursive calls, both of which run. The calls then form a tree rather than a chain and their number grows exponentially — the recursive Fibonacci method, defined as \(F(0) = 0\), \(F(1) = 1\) and \(F(n) = F(n-1) + F(n-2)\), makes 15 calls to produce term 5 and about 2.7 million to produce term 30, because separate branches recompute the same terms.
- Two recursive calls written in the code are not the same as two calls made. Binary search contains two, but only one of them runs on any invocation, so it is not binary recursion.
- Indirect recursion, also called mutual recursion: a method calls a second method which calls the first one back, so the method is re-entered without containing a call to itself.
Recursion and iteration
- Both produce repetition and both can be correct. Recursion adds the cost of a call and a return to every repetition, and one stack frame per level of depth, where iteration uses a fixed amount of memory however many passes it makes.
- Recursion is not faster than iteration and is not automatically easier to debug.
- Recursion reads better when the problem’s own definition is recursive or its structure branches, and when the depth stays modest. Iteration is the better choice for a straightforward sweep, or when the number of repetitions could be large.
The Tower of Hanoi
- Three pegs and a pile of discs of different sizes; one disc moves at a time, only from the top of a peg, and never onto a smaller disc.
- Moving n discs breaks into three steps: move the top n-1 discs to the spare peg, move disc n to the target peg, then move the n-1 discs onto the target peg. The base case is a single disc.
- The recursive calls are always legal because disc n is larger than every disc being moved, so it obstructs nothing while the smaller discs are transferred.
- The number of moves satisfies \(M(1) = 1\) and \(M(n) = 2 \times M(n-1) + 1\), giving \(M(n) = 2^n - 1\), and no shorter solution is possible.
- The calls form a tree of \(2^n - 1\) moves but a stack only n frames deep. A tree of calls can be enormous and shallow at the same time; it is the depth, not the total, that the call stack must hold.
11.10 Key Terms
base — the number of distinct digits used by a positional number system; in base b each position counts a multiple of a power of b, rising from right to left and starting at \(b^0\).
base case — the case for which a recursive method returns an answer directly, without calling itself again.
binary recursion — the arrangement in which one invocation of a recursive method makes two recursive calls to itself, both of which are carried out.
binary search — a method of searching a sorted array by comparing the wanted value with the middle element and continuing in only one half of the remaining portion.
call stack — the region of memory in which the stack frames of all calls that have not yet finished are held, the most recent on top.
direct recursion — the arrangement in which a method contains, within its own body, one or more calls to itself.
GCD — greatest common divisor; see below.
greatest common divisor (GCD) — the largest whole number that divides two given whole numbers, not both zero, exactly.
indirect recursion — the arrangement in which a method calls a second method which, directly or through further methods, calls the first method again; also called mutual recursion.
infinite recursion — a recursion whose calls never reach a base case, so that frames accumulate until the stack is full and the program fails with a
StackOverflowError.integer overflow — the silent wrapping round of a result that is too large for the integer type holding it, producing a meaningless value rather than an error.
iteration — repetition produced by a loop, in which control returns to the top of a block until a condition fails.
JDK — Java Development Kit; the standard set of Java tools and library classes assumed by the programs in this book.
last in, first out (LIFO) — the discipline followed by the call stack, in which the item added most recently is the first to be removed.
LIFO — last in, first out; see above.
recursion — the technique of solving a problem by expressing its solution in terms of the solution to a smaller case of the same problem, together with a smallest case answered directly.
recursive case — the case in which a recursive method obtains its answer by calling itself on a strictly smaller problem and combining the returned value with the work that remains.
recursive definition — a definition with at least one clause giving the answer outright for the smallest case and at least one clause giving the answer for a larger case in terms of a smaller one.
recursive method — a method that calls itself, either directly or through another method.
stack frame — the block of memory set aside for one method call, holding its formal arguments, its local variables and the address to return to.
tail recursion — recursion in which the recursive call is the last operation the method performs, leaving no work to be done after it returns.
Tower of Hanoi — a puzzle in which a pile of discs of different sizes must be moved between three pegs, one disc at a time, never placing a disc on a smaller one.
11.11 Points to Ponder
A tail-recursive method can be turned into a loop almost mechanically, and some language systems perform that conversion automatically. If a compiler did the conversion for you, would tail recursion still be worth recognising as a separate idea, or would it become a detail of the machine that a programmer need not think about?
The recursive Fibonacci method mirrors its mathematical definition exactly, and it needs about 2.7 million calls to produce the thirtieth term. A method that keeps two variables in a loop needs twenty-nine additions. When, if ever, is a method worth keeping because it matches its specification, even though a faster method for the same job exists?
Binary search contains two recursive calls in its text but makes only one on any invocation. Some books classify a method by how many calls appear in the code and others by how many are actually made. Which classification tells you more about how the method will behave, and what does the disagreement suggest about defining terms by their appearance rather than by their effect?
The Tower of Hanoi method is three lines long and, for sixty-four discs, would ask a machine to perform more moves than it could complete in the lifetime of the universe. What does that say about the relationship between the length of a program and the amount of work it sets in motion — and about what you can and cannot judge by reading code?
A missing base case stops the program with an error; a wrong base case lets it run and print an answer that is quietly incorrect. Which of these two failures would you rather have in a program you had written, and how should the answer shape the way a recursive method is tested?
Recursion uses the machine’s own call stack to remember suspended work, instead of the programmer building a structure to hold it. Is that a genuine simplification of the problem, or has the same memory cost simply been moved somewhere you cannot see it?
11.12 Objective Questions
- The base case of a recursive method is best described as the case in which the method: [1 mark]
- calls itself with the smallest possible argument
- returns an answer without calling itself again
- uses the fewest local variables
- is called for the first time from
main()
- Which of the following recursive cases is tail recursive? [1 mark]
return n * fact(n - 1);return fib(n - 1) + fib(n - 2);return gcd(b, a % b);return convert(n / base, base) + (n % base);
- The least number of moves needed to transfer six discs in the Tower of Hanoi is: [1 mark]
- 32
- 36
- 63
- 64
- A recursive method whose calls never reach a base case will: [1 mark]
- fail to compile
- return a wrong value and stop
- run until the call stack is full and fail at run time
- be converted into a loop by the compiler
- The stack frames of a set of unfinished method calls are removed in the order: [1 mark]
- first in, first out
- last in, first out
- the order in which the calls were written in the code
- smallest argument first
- Assertion (A): Binary search may be applied only to an array whose elements are in sorted order. Reason (R): The comparison at the middle element tells the method which half of the array can be discarded. Choose the correct option: [1 mark]
- Both A and R are true, and R is the correct explanation of A.
- Both A and R are true, but R is not the correct explanation of A.
- A is true but R is false.
- A is false but R is true.
- Assertion (A): A tail-recursive method in Java uses only one stack frame however deep the recursion goes. Reason (R): In a tail-recursive method no work remains to be done after the recursive call returns. Choose the correct option: [1 mark]
- Both A and R are true, and R is the correct explanation of A.
- Both A and R are true, but R is not the correct explanation of A.
- A is true but R is false.
- A is false but R is true.
- Match each term in Column A with its description in Column B. [1 mark]
| Column A | Column B |
|---|---|
| a. Binary recursion | i. The branch that calls the method on a strictly smaller problem |
| b. Indirect recursion | ii. The block of memory holding one call’s arguments, locals and return address |
| c. Recursive case | iii. One invocation makes two recursive calls, both of which run |
| d. Stack frame | iv. A method is re-entered through a call made by a second method |
Fill in the blanks. [1 mark] For an
intvaluen, the expressionn % 10gives the ______ of the number, andn / 10gives the number with that digit ______.State whether the following is true or false: a method containing two recursive calls in its code necessarily makes two recursive calls every time it runs. [1 mark]
Give the full form of: (i) GCD (ii) LIFO [1 mark]
11.13 Check Your Concepts
Define recursion. State the two conditions a problem must satisfy before it can be solved recursively. [2 marks]
State what a stack frame holds, and explain in one sentence why two unfinished calls to the same method do not interfere with each other’s variables. [2 marks]
Differentiate between tail recursion and binary recursion, giving one example of each from any method you have studied. [3 marks]
Write the recursive definition of the greatest common divisor of two whole numbers, and explain why the pair (a, b) and the pair (b, a mod b) have the same greatest common divisor. [3 marks]
A recursive method converts a whole number to a given base by obtaining the representation of
n / baseand attachingn % baseto it. Explain, using 25 in base 2 as your example, why the remainder must be attached after the recursive call and not before it. [4 marks]State the best-case and worst-case complexity of recursive binary search in big O notation, saying clearly what n counts, and justify each answer by describing what happens at every call. [4 marks]
For the Tower of Hanoi with n discs: state the three steps of the recursive solution; explain why the discs moved during those steps can never break the rule about disc sizes; and derive the total number of moves from the relation \(M(n) = 2 \times M(n-1) + 1\) with \(M(1) = 1\). [6 marks]
Compare recursion and iteration as ways of computing the sum of the first n natural numbers. Your answer should cover the number of additions performed, the memory used in each case, the way each version fails when n is very large, and a reasoned statement of which you would choose and why. [6 marks]
11.14 Output & Debugging
- The following method is part of some class. [3 marks]
void show(int n)
{
if (n > 0)
{
show(n - 1);
System.out.print(n + " ");
}
}- Write the output when
show(4)is invoked. - State the output if the two statements inside the
ifblock were interchanged.
- The following method is part of some class. [3 marks]
int total(int n)
{
if (n == 1)
{
return 1;
}
else
{
return n + total(n - 2);
}
}- State the value returned by
total(7). - State what happens when
total(6)is invoked, and correct the method so that it works for every whole number that is not negative.
- The following method is part of some class. [4 marks]
int f(int n)
{
if (n <= 1)
{
return 1;
}
else
{
return f(n - 1) + f(n - 2);
}
}- State the value returned by
f(5). - State the total number of calls to
f()made by the single callf(5), counting that call itself. - Name the form of recursion this method uses.
- The following method is part of some class. [3 marks]
int count(String s, int p)
{
if (p < 0)
{
return 0;
}
else if (s.charAt(p) == 'A')
{
return 1 + count(s, p - 1);
}
else
{
return count(s, p - 1);
}
}- State the value returned by
count("BANANA", 5). - State in one line what the method computes, apart from being recursive.
- The following method is part of some class. [3 marks]
int q(int n)
{
if (n < 10)
{
return n;
}
else
{
return q(n / 10) * 10 + n % 10;
}
}- State the value returned by
q(4072). - State in one line what the method computes, and suggest one small change that would make it return the digits in reverse order.
11.15 Programming Practice
Write a recursive method
int digits(int n)that returns the number of digits in a whole number n, where n is not negative. A number below 10 has one digit. Submit the algorithm in pseudocode and the method; the rest of the class need not be written. Sample: for 40725 the method returns 5. [4 marks]An array holds n whole numbers in no particular order. Write a recursive method
int largest(int a[], int last)that returns the largest value among the elements from index 0 to indexlast. Submit the algorithm in pseudocode and the method; the rest of the class need not be written. State clearly what the base case is. [4 marks]Design a class
NumPalinto check whether a whole number reads the same forwards and backwards.
Class name: NumPalin
Data members: num, to store the number entered; rev, to store the reverse of the number.
Member methods: NumPalin() — constructor to initialise the data members with legal initial values void accept() — to read a whole number from the keyboard int reverse(int n) — to return the reverse of n using a recursive method void check() — to invoke reverse() and display whether the number is a palindrome, with a suitable message
Submit the complete class including a main() method that creates an object and calls the methods in the correct order, together with a variable description table. Sample input: 20502. Sample form of output: a line stating the number, its reverse, and whether it is a palindrome. [6 marks]
- Design a class
SeriesSumto find the sum of the series \(\frac{1}{1!} + \frac{2}{2!} + \frac{3}{3!} + \cdots\) up to n terms.
Class name: SeriesSum
Data members: n, to store the number of terms; sum, a double to store the sum.
Member methods: SeriesSum(int nn) — parameterised constructor to assign nn to n and 0 to sum int fact(int m) — to return the factorial of m using a recursive method void calculate() — to compute the sum of the series by invoking fact() void display() — to display the number of terms and the sum
Submit the complete class including a main() method that creates an object and calls the methods in the correct order, together with a variable description table. State in one line why the number of terms should be kept small if fact() returns an int. [6 marks]