## 2.3 Recursion

THE IDEA OF CALLING ONE FUNCTION from another immediately suggests the possibility of a function calling *itself*. The function-call mechanism in Java and most modern programming languages supports this possibility, which is known as *recursion*. In this section, we will study examples of elegant and efficient recursive solutions to a variety of problems. Recursion is a powerful programming technique that we use often in this book. Recursive programs are often more compact and easier to understand than their nonrecursive counterparts. Few programmers become sufficiently comfortable with recursion to use it in everyday code, but solving a problem with an elegantly crafted recursive program is a satisfying experience that is certainly accessible to every programmer (even you!).

Recursion is much more than a programming technique. In many settings, it is a useful way to describe the natural world. For example, the recursive tree (to the left) resembles a real tree, and has a natural recursive description. Many, many phenomena are well explained by recursive models. In particular, recursion plays a central role in computer science. It provides a simple computational model that embraces everything that can be computed with any computer; it helps us to organize and to analyze programs; and it is the key to numerous critically important computational applications, ranging from combinatorial search to tree data structures that support information processing to the fast Fourier transform for signal processing.

One important reason to embrace recursion is that it provides a straightforward way to build simple mathematical models that we can use to prove important facts about our programs. The proof technique that we use to do so is known as *mathematical induction*. Generally, we avoid going into the details of mathematical proofs in this book, but you will see in this section that it is worthwhile to understand that point of view and make the effort to convince yourself that recursive programs have the intended effect.

### Your first recursive program

The “Hello, World” for recursion is the *factorial* function, defined for positive integers *n* by the equation

*n* ! = *n* × (*n*–1) × (*n*–2) × ... × 2 × 1

In other words, *n*! is the product of the positive integers less than or equal to *n*. Now, *n*! is easy to compute with a `for` loop, but an even easier method is to use the following recursive function:

public static long factorial(int n)

{

if (n == 1) return 1;

return n * factorial(n-1);

}

This function calls itself. The implementation clearly produces the desired effect. You can persuade yourself that it does so by noting that `factorial()` returns 1 = 1! when *n* is 1 and that if it properly computes the value

(*n*–1) ! = (*n*–1) × (*n*–*2*) × ... × 2 × 1

then it properly computes the value

*n*! =*n*× (*n*–1)!=

*n*× (*n*–1) × (*n*–*2*) × ... × 2 × 1

To compute `factorial(5)`, the recursive function multiplies `5` by `factorial(4)`; to compute `factorial(4)`, it multiplies `4` by `factorial(3)`; and so forth. This process is repeated until calling `factorial(1)`, which directly returns the value `1`. We can trace this computation in precisely the same way that we trace any sequence of function calls. Since we treat all of the calls as being independent copies of the code, the fact that they are recursive is immaterial.

*Function-call trace for factorial(5)*

factorial(5)

factorial(4)

factorial(3)

factorial(2)

factorial(1)

return 1

return 2*1 = 2

return 3*2 = 6

return 4*6 = 24

return 5*24 = 120

Our `factorial()` implementation exhibits the two main components that are required for every recursive function. First, the *base case* returns a value without making any subsequent recursive calls. It does this for one or more special input values for which the function can be evaluated without recursion. For `factorial()`, the base case is *n* = 1. Second, the *reduction step* is the central part of a recursive function. It relates the function at one (or more) arguments to the function evaluated at one (or more) other arguments. For `factorial()`, the reduction step is `n * factorial(n-1)`. All recursive functions must have these two components. Furthermore, the sequence of argument values must converge to the base case. For `factorial()`, the value of *n* decreases by 1 for each call, so the sequence of argument values converges to the base case *n* = 1.

*Values of n! in long*

1 1

2 2

3 6

4 24

5 120

6 720

7 5040

8 40320

9 362880

10 3628800

11 39916800

12 479001600

13 6227020800

14 87178291200

15 1307674368000

16 20922789888000

17 355687428096000

18 6402373705728000

19 121645100408832000

20 2432902008176640000

Tiny programs such as `factorial()` perhaps become slightly clearer if we put the reduction step in an `else` clause. However, adopting this convention for every recursive program would unnecessarily complicate larger programs because it would involve putting most of the code (for the reduction step) within curly braces after the `else`. Instead, we adopt the convention of always putting the base case as the first statement, ending with a `return`, and then devoting the rest of the code to the reduction step.

The `factorial()` implementation itself is not particularly useful in practice because *n*! grows so quickly that the multiplication will overflow a `long` and produce incorrect answers for *n* > 20. But the same technique is effective for computing all sorts of functions. For example, the recursive function

public static double harmonic(int n)

{

if (n == 1) return 1.0;

return harmonic(n-1) + 1.0/n;

}

computes the *n*th harmonic numbers (see PROGRAM 1.3.5) when *n* is small, based on the following equations:

*H*= 1 + 1/2 + ... + 1/_{n}*n*= (1 + 1/2 + ... + 1/(

*n*–1)) + 1/*n*=

*H*_{n}_{–1}+ 1/*n*

Indeed, this same approach is effective for computing, with only a few lines of code, the value of *any* finite sum (or product) for which you have a compact formula. Recursive functions like these are just loops in disguise, but recursion can help us better understand the underlying computation.

### Mathematical induction

Recursive programming is directly related to *mathematical induction*, a technique that is widely used for proving facts about the natural numbers.

Proving that a statement involving an integer *n* is true for infinitely many values of *n* by mathematical induction involves the following two steps:

The

*base case*: prove the statement true for some specific value or values of*n*(usually 0 or 1).The

*induction step*(the central part of the proof): assume the statement to be true for all positive integers less than*n*, then use that fact to prove it true for*n.*

Such a proof suffices to show that the statement is true for *infinitely* many values of *n*: we can start at the base case, and use our proof to establish that the statement is true for each larger value of *n*, one by one.

Everyone’s first induction proof is to demonstrate that the sum of the positive integers less than or equal to *n* is given by the formula *n* (*n* + 1) / 2. That is, we wish to prove that the following equation is valid for all *n* ≥ 1:

1 + 2 + 3 ... + (

*n*–1) +*n*=*n*(*n*+ 1) / 2

The equation is certainly true for *n* = 1 (base case) because 1 = 1(1 + 1) / 2. If we assume it to be true for all positive integers less than *n*, then, in particular, it is true for *n*–1, so

1 + 2 + 3 ... + (

*n*–1) = (*n*–1)*n*/ 2

and we can add *n* to both sides of this equation and simplify to get the desired equation (induction step).

Every time we write a recursive program, we need mathematical induction to be convinced that the program has the desired effect. The correspondence between induction and recursion is self-evident. The difference in nomenclature indicates a difference in outlook: in a recursive program, our outlook is to get a computation done by reducing to a smaller problem, so we use the term *reduction step*; in an induction proof, our outlook is to establish the truth of the statement for larger problems, so we use the term *induction step*.

When we write recursive programs we usually do not write down a full formal proof that they produce the desired result, but we are always dependent upon the existence of such a proof. We often appeal to an informal induction proof to convince ourselves that a recursive program operates as expected. For example, we just discussed an informal proof to become convinced that `factorial()` computes the product of the positive integers less than or equal to *n*.

*Program 2.3.1 Euclid’s algorithm*

public class Euclid

{

public static int gcd(int p, int q)

{

if (q == 0) return p;

return gcd(q, p % q);

}

public static void main(String[] args)

{

int p = Integer.parseInt(args[0]);

int q = Integer.parseInt(args[1]);

int divisor = gcd(p, q);

StdOut.println(divisor);

}

}

p, q |arguments

divisor |greatest common divisor

%java Euclid 1440 408

24

%java Euclid 314159 271828

1

*This program prints the greatest common divisor of its two command-line arguments, using a recursive implementation of Euclid’s algorithm.*

### Euclid’s algorithm

The *greatest common divisor* (gcd) of two positive integers is the largest integer that divides evenly into both of them. For example, the greatest common divisor of 102 and 68 is 34 since both 102 and 68 are multiples of 34, but no integer larger than 34 divides evenly into 102 and 68. You may recall learning about the greatest common divisor when you learned to reduce fractions. For example, we can simplify 68/102 to 2/3 by dividing both numerator and denominator by 34, their gcd. Finding the gcd of huge numbers is an important problem that arises in many commercial applications, including the famous RSA cryptosystem.

We can efficiently compute the gcd using the following property, which holds for positive integers *p* and *q*:

*If p > q, the gcd of p and q is the same as the gcd of q and p % q.*

To convince yourself of this fact, first note that the gcd of *p* and *q* is the same as the gcd of *q* and *p*–*q*, because a number divides both *p* and *q* if and only if it divides both *q* and *p*–*q*. By the same argument, *q* and *p*–2*q*, *q* and *p*–3*q*, and so forth have the same gcd, and one way to compute *p* % *q* is to subtract *q* from *p* until getting a number less than *q*.

The static method `gcd()` in `Euclid` (PROGRAM 2.3.1) is a compact recursive function whose reduction step is based on this property. The base case is when `q` is `0`, with `gcd(p, 0) = p`. To see that the reduction step converges to the base case, observe that the second argument value strictly decreases in each recursive call since `p % q < q`. If `p < q`, the first recursive call effectively switches the order of the two arguments. In fact, the second argument value decreases by at least a factor of 2 for every second recursive call, so the sequence of argument values quickly converges to the base case (see EXERCISE 2.3.11). This recursive solution to the problem of computing the greatest common divisor is known as *Euclid’s algorithm* and is one of the oldest known algorithms—it is more than 2,000 years old.

gcd(1440, 408)

gcd(408, 216)

gcd(216, 192)

gcd(192, 24)

gcd(24, 0)

return 24

return 24

return 24

return 24

return 24

*Function-call trace for gcd()*

### Towers of Hanoi

No discussion of recursion would be complete without the ancient *towers of Hanoi* problem. In this problem, we have three poles and *n* discs that fit onto the poles. The discs differ in size and are initially stacked on one of the poles, in order from largest (disc *n*) at the bottom to smallest (disc 1) at the top. The task is to move all *n* discs to another pole, while obeying the following rules:

Move only one disc at a time.

Never place a larger disc on a smaller one.

One legend says that the world will end when a certain group of monks accomplishes this task in a temple with 64 golden discs on three diamond needles. But how can the monks accomplish the task at all, playing by the rules?

To solve the problem, our goal is to issue a sequence of instructions for moving the discs. We assume that the poles are arranged in a row, and that each instruction to move a disc specifies its number and whether to move it left or right. If a disc is on the left pole, an instruction to move left means to wrap to the right pole; if a disc is on the right pole, an instruction to move right means to wrap to the left pole. When the discs are all on one pole, there are two possible moves (move the smallest disc left or right); otherwise, there are three possible moves (move the smallest disc left or right, or make the one legal move involving the other two poles). Choosing among these possibilities on each move to achieve the goal is a challenge that requires a plan. Recursion provides just the plan that we need, based on the following idea: first we move the top *n*–1 discs to an empty pole, then we move the largest disc to the other empty pole (where it does not interfere with the smaller ones), and then we complete the job by moving the *n*–1 discs onto the largest disc.

`TowersOfHanoi` (PROGRAM 2.3.2) is a direct implementation of this recursive strategy. It takes a command-line argument `n` and prints the solution to the towers of Hanoi problem on `n` discs. The recursive function `moves()` prints the sequence of moves to move the stack of discs to the left (if the argument `left` is `true`) or to the right (if `left` is `false`). It does so exactly according to the plan just described.

### Function-call trees

To better understand the behavior of modular programs that have multiple recursive calls (such as `TowersOfHanoi`), we use a visual representation known as a *function-call tree*. Specifically, we represent each method call as a *tree node*, depicted as a circle labeled with the values of the arguments for that call. Below each tree node, we draw the tree nodes corresponding to each call in that use of the method (in order from left to right) and lines connecting to them. This diagram contains all the information we need to understand the behavior of the program. It contains a tree node for each function call.

We can use function-call trees to understand the behavior of any modular program, but they are particularly useful in exposing the behavior of recursive programs. For example, the tree corresponding to a call to `move()` in `TowersOfHanoi` is easy to construct. Start by drawing a tree node labeled with the values of the command-line arguments. The first argument is the number of discs in the pile to be moved (and the label of the disc to actually be moved); the second is the direction to move the disc. For clarity, we depict the direction (a `boolean` value) as an arrow that points left or right, since that is our interpretation of the value—the direction to move the piece. Then draw two tree nodes below with the number of discs decremented by 1 and the direction switched, and continue doing so until only nodes with labels corresponding to a first argument value 1 have no nodes below them. These nodes correspond to calls on `moves()` that do not lead to further recursive calls.

*Program 2.3.2 Towers of Hanoi*

public class TowersOfHanoi

{

public static void moves(int n, boolean left)

{

if (n == 0) return;

moves(n-1, !left);

if (left) StdOut.println(n + " left");

else StdOut.println(n + " right");

moves(n-1, !left);

}

public static void main(String[] args)

{ // Read n, print moves to move n discs left.

int n = Integer.parseInt(args[0]);

moves(n, true);

}

}

n |number of discs

left |direction to move pile

*The recursive method moves() prints the moves needed to move n discs to the left (if left is true) or to the right (if left is false).*

%java TowersOfHanoi 1

1 left

%java TowersOfHanoi 2

1 right

2 left

1 right

%java TowersOfHanoi 3

1 left

2 right

1 left

3 left

1 left

2 right

1 left

% javaTowersOfHanoi 4

1 right

2 left

1 right

3 right

1 right

2 left

1 right

4 left

1 right

2 left

1 right

3 right

1 right

2 left

1 right

Take a moment to study the function-call tree depicted earlier in this section and to compare it with the corresponding function-call trace depicted at right. When you do so, you will see that the recursion tree is just a compact representation of the trace. In particular, reading the node labels from left to right gives the moves needed to solve the problem.

Moreover, when you study the tree, you probably notice several patterns, including the following two:

Alternate moves involve the smallest disc.

That disc always moves in the same direction.

These observations are relevant because they give a solution to the problem that does not require recursion (or even a computer): every other move involves the smallest disc (including the first and last), and each intervening move is the only legal move at the time not involving the smallest disc. We can *prove* that this approach produces the same outcome as the recursive program, using induction. Having started centuries ago without the benefit of a computer, perhaps our monks are using this approach.

Trees are relevant and important in understanding recursion because the tree is a quintessential recursive object. As an abstract mathematical model, trees play an essential role in many applications, and in CHAPTER 4, we will consider the use of trees as a computational model to structure data for efficient processing.

### Exponential time

One advantage of using recursion is that often we can develop mathematical models that allow us to prove important facts about the behavior of recursive programs. For the towers of Hanoi problem, we can estimate the amount of time until the end of the world (assuming that the legend is true). This exercise is important not just because it tells us that the end of the world is quite far off (even if the legend is true), but also because it provides insight that can help us avoid writing programs that will not finish until then.

The mathematical model for the towers of Hanoi problem is simple: if we define the function *T*(*n*) to be the number of discs moved by `TowersOfHanoi` to solve an *n*-disc problem, then the recursive code implies that *T*(*n*) must satisfy the following equation:

*T*(*n*) = 2*T*(*n*–1) + 1 for*n*> 1, with*T*(1) = 1

Such an equation is known in discrete mathematics as a *recurrence relation*. Recurrence relations naturally arise in the study of recursive programs. We can often use them to derive a closed-form expression for the quantity of interest. For *T*(*n*), you may have already guessed from the initial values *T*(1) = 1, *T*(2) = 3, *T*(3), = 7, and *T*(4) = 15 that *T*(*n*) = 2 * ^{n}* – 1. The recurrence relation provides a way to

*prove*this to be true, by mathematical induction:

*Base case*: T(1) = 2– 1 = 1^{n}*Induction step*: if*T*(*n*–1)= 2^{n–1}– 1,*T*(*n*) = 2 (2^{n–1}– 1) + 1 = 2– 1^{n}

Therefore, by induction, *T*(*n*) = 2* ^{n}* – 1 for all

*n*> 0. The minimum possible number of moves also satisfies the same recurrence (see EXERCISE 2.3.11).

Knowing the value of *T*(*n*), we can estimate the amount of time required to perform all the moves. If the monks move discs at the rate of one per second, it would take more than one week for them to finish a 20-disc problem, more than 34 years to finish a 30-disc problem, and more than 348 *centuries* for them to finish a 40-disc problem (assuming that they do not make a mistake). The 64-disc problem would take more than 5.8 *billion* centuries. The end of the world is likely to be even further off than that because those monks presumably never have had the benefit of using PROGRAM 2.3.2, and might not be able to move the discs so rapidly or to figure out so quickly which disc to move next.

Even computers are no match for exponential growth. A computer that can do a billion operations per second will still take centuries to do 2^{64} operations, and no computer will ever do 2^{1,000} operations, say. The lesson is profound: with recursion, you can easily write simple short programs that take exponential time, but they simply will not run to completion when you try to run them for large *n*. Novices are often skeptical of this basic fact, so it is worth your while to pause now to think about it. To convince yourself that it is true, take the print statements out of `TowersOfHanoi` and run it for increasing values of *n* starting at 20. You can easily verify that each time you increase the value of *n* by 1, the running time doubles, and you will quickly lose patience waiting for it to finish. If you wait for an hour for some value of *n*, you will wait more than a day for *n* + 5, more than a month for *n* + 10, and more than a century for *n* + 20 (no one has *that* much patience). Your computer is just not fast enough to run every short Java program that you write, no matter how simple the program might seem! *Beware of programs that might require exponential time.*

We are often interested in predicting the running time of our programs. In SECTION 4.1, we will discuss the use of the same process that we just used to help estimate the running time of other programs.

### Gray codes

The towers of Hanoi problem is no toy. It is intimately related to basic algorithms for manipulating numbers and discrete objects. As an example, we consider *Gray codes*, a mathematical abstraction with numerous applications.

The playwright Samuel Beckett, perhaps best known for *Waiting for Godot*, wrote a play called *Quad* that had the following property: starting with an empty stage, characters enter and exit one at a time so that each subset of characters on the stage appears exactly once. How did Beckett generate the stage directions for this play?

One way to represent a subset of *n* discrete objects is to use a string of *n* bits. For Beckett’s problem, we use a 4-bit string, with bits numbered from right to left and a bit value of 1 indicating the character onstage. For example, the string `0 1 0 1` corresponds to the scene with characters `3` and `1` onstage. This representation gives a quick proof of a basic fact: *the number different subsets of n objects is exactly* 2 * ^{n}*.

*Quad*has four characters, so there are 2

^{4}= 16 different scenes. Our task is to generate the stage directions.

An *n*-bit *Gray code* is a list of the 2* ^{n}* different

*n*-bit binary numbers such that each element in the list differs in precisely one bit from its predecessor. Gray codes directly apply to Beckett’s problem because changing the value of a bit from 0 to 1 corresponds to a character entering the subset onstage; changing a bit from 1 to 0 corresponds to a character exiting the subset.

How do we generate a Gray code? A recursive plan that is very similar to the one that we used for the towers of Hanoi problem is effective. The *n*-bit *binary-reflected Gray code* is defined recursively as follows:

The (

*n*–1) bit code, with 0 prepended to each word, followed byThe (

*n*–1) bit code*in reverse order*, with 1 prepended to each word

The 0-bit code is defined to be empty, so the 1-bit code is 0 followed by 1. From this recursive definition, we can verify by induction that the *n*-bit binary reflected Gray code has the required property: adjacent codewords differ in one bit position. It is true by the inductive hypothesis, except possibly for the last codeword in the first half and the first codeword in the second half: this pair differs only in their first bit.

The recursive definition leads, after some careful thought, to the implementation in `Beckett` (PROGRAM 2.3.3) for printing Beckett’s stage directions. This program is remarkably similar to `TowersOfHanoi`. Indeed, except for nomenclature, the only difference is in the values of the second arguments in the recursive calls!

As with the directions in `TowersOfHanoi`, the enter and exit directions are redundant in `Beckett`, since `exit` is issued only when an actor is onstage, and `enter` is issued only when an actor is not onstage. Indeed, both `Beckett` and `TowersOfHanoi` directly involve the ruler function that we considered in one of our first programs (PROGRAM 1.2.1). Without the printing instructions, they both implement a simple recursive function that could allow `Ruler` to print the values of the ruler function for any value given as a command-line argument.

Gray codes have many applications, ranging from analog-to-digital converters to experimental design. They have been used in pulse code communication, the minimization of logic circuits, and hypercube architectures, and were even proposed to organize books on library shelves.

*Program 2.3.3 Gray code*

public class Beckett

{

public static void moves(int n, boolean enter)

{

if (n == 0) return;

moves(n-1, true);

if (enter) StdOut.println("enter " + n);

else StdOut.println("exit " + n);

moves(n-1, false);

}

public static void main(String[] args)

{

int n = Integer.parseInt(args[0]);

moves(n, true);

}

}

n |number of actors

enter |stage direction

*This recursive program gives Beckett’s stage instructions (the bit positions that change in a binary-reflected Gray code). The bit position that changes is precisely described by the ruler function, and (of course) each actor alternately enters and exits.*

%java Beckett 1

enter 1

%java Beckett 2

enter 1

enter 2

exit 1

%java Beckett 3

enter 1

enter 2

exit 1

enter 3

enter 1

exit 2

exit 1

%java Beckett 4

enter 1

enter 2

exit 1

enter 3

enter 1

exit 2

exit 1

enter 4

enter 1

enter 2

exit 1

exit 3

enter 1

exit 2

exit 1

### Recursive graphics

Simple recursive drawing schemes can lead to pictures that are remarkably intricate. Recursive drawings not only relate to numerous applications, but also provide an appealing platform for developing a better understanding of properties of recursive functions, because we can watch the process of a recursive figure taking shape.

As a first simple example, consider `Htree` (PROGRAM 2.3.4), which, given a command-line argument *n*, draws an *H-tree of order n*, defined as follows: The base case is to draw nothing for *n* = 0. The reduction step is to draw, within the unit square

three lines in the shape of the letter H

four H-trees of order

*n*–1, one centered at each tip of the H with the additional proviso that the H-trees of order*n*–1 are halved in size.

Drawings like these have many practical applications. For example, consider a cable company that needs to run cable to all of the homes distributed throughout its region. A reasonable strategy is to use an H-tree to get the signal to a suitable number of centers distributed throughout the region, then run cables connecting each home to the nearest center. The same problem is faced by computer designers who want to distribute power or signal throughout an integrated circuit chip.

Though every drawing is in a fixed-size window, H-trees certainly exhibit exponential growth. An H-tree of order *n* connects 4* ^{n}* centers, so you would be trying to plot more than a million lines with

*n*= 10,

*and*more than a billion with

*n*= 15. The program will certainly not finish the drawing with

*n*= 30.

If you take a moment to run `Htree` on your computer for a drawing that takes a minute or so to complete, you will, just by watching the drawing progress, have the opportunity to gain substantial insight into the nature of recursive programs, because you can see the *order* in which the H figures appear and how they form into H-trees. An even more instructive exercise, which derives from the fact that the same drawing results no matter in which order the recursive `draw()` calls and the `StdDraw.line()` calls appear, is to observe the effect of rearranging the order of these calls on the order in which the lines appear in the emerging drawing (see EXERCISE 2.3.14).

*Program 2.3.4 Recursive graphics*

public class Htree

{

public static void draw(int n, double size, double x, double y)

{ // Draw an H-tree centered at x, y

// of depth n and given size.

if (n == 0) return;

double x0 = x - size/2, x1 = x + size/2;

double y0 = y - size/2, y1 = y + size/2;

StdDraw.line(x0, y, x1, y);

StdDraw.line(x0, y0, x0, y1);

StdDraw.line(x1, y0, x1, y1);

draw(n-1, size/2, x0, y0);

draw(n-1, size/2, x0, y1);

draw(n-1, size/2, x1, y0);

draw(n-1, size/2, x1, y1);

}

public static void main(String[] args)

{

int n = Integer.parseInt(args[0]);

draw(n, 0.5, 0.5, 0.5);

}

}

n |depth

size |line length

x, y |center

*The function draw() draws three lines, each of length size, in the shape of the letter H, centered at (x, y). Then, it calls itself recursively for each of the four tips, halving the size argument in each call and using an integer argument n to control the depth of the recursion.*

### Brownian bridge

An H-tree is a simple example of a *fractal*: a geometric shape that can be divided into parts, each of which is (approximately) a reduced-size copy of the original. Fractals are easy to produce with recursive programs, although scientists, mathematicians, and programmers study them from many different points of view. We have already encountered fractals several times in this book—for example, `IFS` (PROGRAM 2.2.3).

The study of fractals plays an important and lasting role in artistic expression, economic analysis, and scientific discovery. Artists and scientists use fractals to build compact models of complex shapes that arise in nature and resist description using conventional geometry, such as clouds, plants, mountains, riverbeds, human skin, and many others. Economists use fractals to model function graphs of economic indicators.

*Fractional Brownian motion* is a mathematical model for creating realistic fractal models for many naturally rugged shapes. It is used in computational finance and in the study of many natural phenomena, including ocean flows and nerve membranes. Computing the exact fractals specified by the model can be a difficult challenge, but it is not difficult to compute approximations with recursive programs.

`Brownian` (PROGRAM 2.3.5) produces a function graph that approximates a simple example of fractional Brownian motion known as a *Brownian bridge* and closely related functions. You can think of this graph as a random walk that connects the two points (*x*_{0}, *y*_{0}) and (*x*_{1}, *y*_{1}), controlled by a few parameters. The implementation is based on the *midpoint displacement method*, which is a recursive plan for drawing the plot within the *x*-interval [*x*_{0}, *x*_{1}]. The base case (when the length of the interval is smaller than a given tolerance) is to draw a straight line connecting the two endpoints. The reduction case is to divide the interval into two halves, proceeding as follows:

Compute the midpoint (

*x*,_{m}*y*) of the interval._{m}Add to the

*y*-coordinate*y*of the midpoint a random value δ, drawn from the Gaussian distribution with mean 0 and a given variance._{m}Recur on the subintervals, dividing the variance by a given scaling factor

*s*.

The shape of the curve is controlled by two parameters: the *volatility* (initial value of the variance) controls the distance the function graph strays from the straight line connecting the points, and *the Hurst exponent* controls the smoothness of the curve. We denote the Hurst exponent by *H* and divide the variance by 2^{2H} at each recursive level. When *H* is 1/2 (halved at each level), the curve is a Brownian bridge—a continuous version of the gambler’s ruin problem (see PROGRAM 1.3.8). When 0 *< H <* 1/2, the displacements tend to increase, resulting in a rougher curve. Finally, when 2 *> H* > 1/2, the displacements tend to decrease, resulting in a smoother curve. The value 2 –*H* is known as the *fractal dimension* of the curve.

*Program 2.3.5 Brownian bridge*

public class Brownian

{

public static void curve(double x0, double y0,

double x1, double y1,

double var, double s)

{

if (x1 - x0 < 0.01)

{

StdDraw.line(x0, y0, x1, y1);

return;

}

double xm = (x0 + x1) / 2;

double ym = (y0 + y1) / 2;

double delta = StdRandom.gaussian(0, Math.sqrt(var));

curve(x0, y0, xm, ym+delta, var/s, s);

curve(xm, ym+delta, x1, y1, var/s, s);

}

public static void main(String[] args)

{

double hurst = Double.parseDouble(args[0]);

double s = Math.pow(2, 2*hurst);

curve(0, 0.5, 1.0, 0.5, 0.01, s);

}

}

x0, y0 |left endpoint

x1, y1 |right endpoint

xm, ym |middle

delta |displacement

var |variance

hurst |Hurst exponent

*By adding a small, random Gaussian to a recursive program that would otherwise plot a straight line, we get fractal curves. The command-line argument hurst, known as the Hurst exponent, controls the smoothness of the curves.*

The volatility and initial endpoints of the interval have to do with scale and positioning. The `main()` test client in `Brownian` allows you to experiment with the Hurst exponent. With values larger than 1/2, you get plots that look something like the horizon in a mountainous landscape; with values smaller than 1/2, you get plots similar to those you might see for the value of a stock index.

Extending the midpoint displacement method to two dimensions yields fractals known as *plasma clouds*. To draw a rectangular plasma cloud, we use a recursive plan where the base case is to draw a rectangle of a given color and the reduction step is to draw a plasma cloud in each of the four quadrants with colors that are perturbed from the average with a random Gaussian. Using the same volatility and smoothness controls as in `Brownian`, we can produce synthetic clouds that are remarkably realistic. We can use the same code to produce synthetic terrain, by interpreting the color value as the altitude. Variants of this scheme are widely used in the entertainment industry to generate background scenery for movies and games.

### Pitfalls of recursion

By now, you are perhaps persuaded that recursion can help you to write compact and elegant programs. As you begin to craft your own recursive programs, you need to be aware of several common pitfalls that can arise. We have already discussed one of them in some detail (the running time of your program might grow exponentially). Once identified, these problems are generally not difficult to overcome, but you will learn to be very careful to avoid them when writing recursive programs.

#### Missing base case

Consider the following recursive function, which is supposed to compute harmonic numbers, but is missing a base case:

public static double harmonic(int n)

{

return harmonic(n-1) + 1.0/n;

}

If you run a client that calls this function, it will repeatedly call itself and never return, so your program will never terminate. You probably already have encountered infinite loops, where you invoke your program and nothing happens (or perhaps you get an unending sequence of printed output). With infinite recursion, however, the result is different because the system keeps track of each recursive call (using a mechanism that we will discuss in SECTION 4.3, based on a data structure known as a *stack*) and eventually runs out of memory trying to do so. Eventually, Java reports a `StackOverflowError` at run time. When you write a recursive program, you should always try to convince yourself that it has the desired effect by an informal argument based on mathematical induction. Doing so might uncover a missing base case.

#### No guarantee of convergence

Another common problem is to include within a recursive function a recursive call to solve a subproblem that is not smaller than the original problem. For example, the following method goes into an infinite recursive loop for any value of its argument (except `1`) because the sequence of argument values does not converge to the base case:

public static double harmonic(int n)

{

if (n == 1) return 1.0;

return harmonic(n) + 1.0/n;

}

Bugs like this one are easy to spot, but subtle versions of the same problem can be harder to identify. You may find several examples in the exercises at the end of this section.

#### Excessive memory requirements

If a function calls itself recursively an excessive number of times before returning, the memory required by Java to keep track of the recursive calls may be prohibitive, resulting in a `StackOverflowError`. To get an idea of how much memory is involved, run a small set of experiments using our recursive function for computing the harmonic numbers for increasing values of `n`:

public static double harmonic(int n)

{

if (n == 1) return 1.0;

return harmonic(n-1) + 1.0/n;

}

The point at which you get `StackOverflowError` will give you some idea of how much memory Java uses to implement recursion. By contrast, you can run PROGRAM 1.3.5 to compute *H _{n}* for huge

*n*using only a tiny bit of memory.

#### Excessive recomputation

The temptation to write a simple recursive function to solve a problem must always be tempered by the understanding that a function might take exponential time (unnecessarily) due to excessive recomputation. This effect is possible even in the simplest recursive functions, and you certainly need to learn to avoid it. For example, the *Fibonacci sequence*

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...

is defined by the recurrence *F _{n} = F_{n}*

_{–1}+

*F*

_{n}_{–2}for

*n*≥ 2 with

*F*

_{0}= 0 and

*F*

_{1}= 1. The Fibonacci sequence has many interesting properties and arise in numerous applications. A novice programmer might implement this recursive function to compute numbers in the Fibonacci sequence:

// Warning: this function is spectacularly inefficient.

public static long fibonacci(int n)

{

if (n == 0) return 0;

if (n == 1) return 1;

return fibonacci(n-1) + fibonacci(n-2);

}

*Wrong way to compute Fibonacci numbers*

fibonacci(8)

fibonacci(7)

fibonacci(6)

fibonacci(5)

fibonacci(4)

fibonacci(3)

fibonacci(2)

fibonacci(1)

return 1

fibonacci(0)

return 0

return 1

fibonacci(1)

return 1

return 2

fibonacci(2)

fibonacci(1)

return 1

fibonacci(0)

return 0

return 1

return 3

fibonacci(3)

fibonacci(2)

fibonacci(1)

return 1

fibonacci(0)

return 0

return 1

fibonacci(1)

return 1

return 2

return 5

fibonacci(4)

fibonacci(3)

fibonacci(2)

.

.

.

However, this function is spectacularly inefficient! Novice programmers often refuse to believe this fact, and run code like this expecting that the computer is certainly fast enough to crank out an answer. Go ahead; see if your computer is fast enough to use this function to compute `fibonacci(50)`. To see why it is futile to do so, consider what the function does to compute `fibonacci(8) = 21`. It first computes `fibonacci(7) = 13` and `fibonacci(6) = 8`. To compute `fibonacci(7)`, it recursively computes `fibonacci(6) = 8` *again* and `fibonacci(5) = 5`. Things rapidly get worse because both times it computes `fibonacci(6)`, it ignores the fact that it already computed `fibonacci(5)`, and so forth. In fact, the number of times this program computes `fibonacci(1)` when computing `fibonacci(n)` is precisely *F _{n}* (see EXERCISE 2.3.12). The mistake of recomputation is compounded exponentially. As an example,

`fibonacci(200)`makes F

_{200}> 10

^{43}recursive calls to

`fibonacci(1)`! No imaginable computer will ever be able to do this many calculations.

*Beware of programs that might require exponential time.*Many calculations that arise and find natural expression as recursive functions fall into this category. Do not fall into the trap of implementing and trying to run them.

Next, we consider a systematic technique known as *dynamic programming*, an elegant technique for avoiding such problems. The idea is to avoid the excessive recomputation inherent in some recursive functions by saving away the previously computed values for later reuse, instead of constantly recomputing them.

### Dynamic programming

A general approach to implementing recursive programs, known as *dynamic programming*, provides effective and elegant solutions to a wide class of problems. The basic idea is to recursively divide a complex problem into a number of simpler subproblems; store the answer to each of these subproblems; and, ultimately, use the stored answers to solve the original problem. By solving each subproblem only once (instead of over and over), this technique avoids a potential exponential blow-up in the running time.

For example, if our original problem is to compute the *n*th Fibonacci number, then it is natural to define *n* + 1 subproblems, where subproblem *i* is to compute the *i*th Fibonacci number for each 0 ≤ *i* ≤ *n*. We can solve subproblem *i* easily if we already know the solutions to smaller subproblems—specifically, subproblems *i*–1 and *i*–2. Moreover, the solution to our original problem is simply the solution to one of the subproblems—subproblem *n*.

#### Top-down dynamic programming

In *top-down* dynamic programming, we store or *cache* the result of each subproblem that we solve, so that the next time we need to solve the same subproblem, we can use the cached values instead of solving the subproblem from scratch. For our Fibonacci example, we use an array `f[]` to store the Fibonacci numbers that have already been computed. We accomplish this in Java by using a `static` variable, also known as a *class variable* or *global variable*, that is declared outside of any method. This allows us to save information from one function call to the next.

Top-down dynamic programming is also known as *memoization* because it avoids duplicating work by *remembering* the results of function calls.

#### Bottom-up dynamic programming

In *bottom-up* dynamic programming, we compute solutions to *all* of the subproblems, starting with the “simplest” subproblems and gradually building up solutions to more and more complicated subproblems. To apply bottom-up dynamic programming, we must order the subproblems so that each subsequent subproblem can be solved by combining solutions to subproblems earlier in the order (which have already been solved). For our Fibonacci example, this is easy: solve the subproblems in the order 0, 1, and 2, and so forth. By the time we need to solve subproblem *i*, we have already solved all smaller subproblems—in particular, subproblems *i*–1 and *i*–2.

public static long fibonacci(int n)

{

int[] f = new int[n+1];

f[0] = 0;

f[1] = 1;

for (int i = 2; i <= n; i++)

f[i] = f[i-1] + f[i-2];

return f[n];

}

When the ordering of the subproblems is clear, and space is available to store all the solutions, bottom-up dynamic programming is a very effective approach.

Next, we consider a more sophisticated application of dynamic programming, where the order of solving the subproblems is not so clear (until you see it). Unlike the problem of computing Fibonacci numbers, this problem would be much more difficult to solve without thinking recursively and also applying a bottom-up dynamic programming approach.

#### Longest common subsequence problem

We consider a fundamental string-processing problem that arises in computational biology and other domains. Given two strings *x* and *y*, we wish to determine how *similar* they are. Some examples include comparing two DNA sequences for homology, two English words for spelling, or two Java files for repeated code. One measure of similarity is the length of the *longest common subsequence* (LCS). If we delete some characters from *x* and some characters from *y*, and the resulting two strings are equal, we call the resulting string a *common subsequence*. The LCS problem is to find a common subsequence of two strings that is as long as possible. For example, the LCS of `GGCACCACG` and `ACGGCGGATACG` is `GGCAACG`, a string of length 7.

Algorithms to compute the LCS are used in data comparison programs like the `diff` command in Unix, which has been used for decades by programmers wanting to understand differences and similarities in their text files. Similar algorithms play important roles in scientific applications, such as the Smith–Waterman algorithm in computational biology and the Viterbi algorithm in digital communications theory.

#### LCS recurrence

Now we describe a recursive formulation that enables us to find the LSC of two given strings `s` and `t`. Let `m` and `n` be the lengths of `s` and `t`, respectively. We use the notation `s[i..m)` to denote the *suffix* of `s` starting at index `i`, and `t[j..n)` to denote the suffix of `t` starting at index `j`. On the one hand, if `s` and `t` begin with the same character, then the LCS of `x` and `y` contains that first character. Thus, our problem reduces to finding the LCS of the suffixes `s[1..m)` and `t[1..n)`. On the other hand, if `s` and `t` begin with different characters, both characters cannot be part of a common subsequence, so we can safely discard one or the other. In either case, the problem reduces to finding the LCS of two strings—either `s[0..m)` and `t[1..n)` or `s[1..m)` and `t[0..n)`—one of which is strictly shorter. In general, if we let `opt[i][j]` denote the length of the LCS of the suffixes `s[i..m)` and `t[j..m)`, then the following recurrence expresses `opt[i][j]` in terms of the length of the LCS for shorter suffixes.

0 if i = m or j = n

opt[i][j] = opt[i+1, j+1] + 1 if s[i] = t[j]

max(opt[i, j+1], opt[i+1, j]) otherwise

#### Dynamic programming solution

`LongestCommonSubsequence` (PROGRAM 2.3.6) begins with a bottom-up dynamic programming approach to solving this recurrence. We maintain a two-dimensional array `opt[i][j]` that stores the length of the LCS of the suffixes `s[i..m)` and `t[j..n)`. Initially, the bottom row (the values for `i = m`) and the right column (the values for `j = n`) are 0. These are the initial values. From the recurrence, the order of the rest of the computation is clear: we start with `opt[m][n] = 1`. Then, as long as we decrease either `i` or `j` or both, we know that we will have computed what we need to compute `opt[i][j]`, since the two options involve an `opt[][]` entry with a larger value of `i` or `j` or both. The method `lcs()` in PROGRAM 2.3.6 computes the elements in `opt[][]` by filling in values in rows from bottom to top (`i = m-1` to `0`) and from right to left in each row (`j = n-1` to `0`). The alternative choice of filling in values in columns from right to left and from bottom to top in each row would work as well. The above diagram has a blue arrow pointing to each entry that indicates which value was used to compute it. (When there is a tie in computing the maximum, both options are shown.)

*Program 2.3.6 Longest common subsequence*

public class LongestCommonSubsequence

{

public static String lcs(String s, String t)

{ // Compute length of LCS for all subproblems.

int m = s.length(), n = t.length();

int[][] opt = new int[m+1][n+1];

for (int i = m-1; i >= 0; i--)

for (int j = n-1; j >= 0; j--)

if (s.charAt(i) == t.charAt(j))

opt[i][j] = opt[i+1][j+1] + 1;

else

opt[i][j] = Math.max(opt[i+1][j], opt[i][j+1]);

// Recover LCS itself.

String lcs = "";

int i = 0, j = 0;

while(i < m && j < n)

{

if (s.charAt(i) == t.charAt(j))

{

lcs += s.charAt(i);

i++;

j++;

}

else if (opt[i+1][j] >= opt[i][j+1]) i++;

else j++;

}

return lcs;

}

public static void main(String[] args)

{ StdOut.println(lcs(args[0], args[1])); }

}

s, t |two strings

m, n |lengths of two strings

opt[i][j] |length of LCS ofx[i..m)andy[j..n)

lcs |longest common subsequence

*The function lcs() computes and returns the LCS of two strings x and y using bottom-up dynamic programming. The method call s.charAt(i) returns character i of string s.*

%java LongestCommonSubsequence GGCACCACG ACGGCGGATACG

GGCAACG

The final challenge is to recover the longest common subsequence itself, not just its length. The key idea is to retrace the steps of the dynamic programming algorithm *backward*, rediscovering the path of choices (highlighted in gray in the diagram) from `opt[0][0]` to `opt[m][n]`. To determine the choice that led to `opt[i][j]`, we consider the three possibilities:

The character

`s[i]`equals`t[j]`. In this case, we must have`opt[i][j] = opt[i+1][j+1] + 1`, and the next character in the LCS is`s[i]`(or`t[j]`), so we include the character`s[i]`(or`t[j]`) in the LCS and continue tracing back from`opt[i+1][j+1]`.The LCS does not contain

`s[i]`. In this case,`opt[i][j] = opt[i+1][j]`and we continue tracing back from`opt[i+1][j]`.The LCS does not contain

`t[j]`. In this case,`opt[i][j] = opt[i][j+1]`and we continue tracing back from`opt[i][j+1]`.

We begin tracing back at `opt[0][0]` and continue until we reach `opt[m][n]`. At each step in the traceback either `i` increases or `j` increases (or both), so the process terminates after at most `m + n` iterations of the `while` loop.

DYNAMIC PROGRAMMING IS A FUNDAMENTAL ALGORITHM design paradigm, intimately linked to recursion. If you take later courses in algorithms or operations research, you are sure to learn more about it. The idea of recursion is fundamental in computation, and the idea of avoiding recomputation of values that have been computed before is certainly a natural one. Not all problems immediately lend themselves to a recursive formulation, and not all recursive formulations admit an order of computation that easily avoids recomputation—arranging for both can seem a bit miraculous when one first encounters it, as you have just seen for the LCS. problem.

### Perspective

Programmers who do not use recursion are missing two opportunities. First recursion leads to compact solutions to complex problems. Second, recursive solutions embody an argument that the program operates as anticipated. In the early days of computing, the overhead associated with recursive programs was prohibitive in some systems, and many people avoided recursion. In modern systems like Java, recursion is often the method of choice.

Recursive functions truly illustrate the power of a carefully articulated abstraction. While the concept of a function having the ability to call itself seems absurd to many people at first, the many examples that we have considered are certainly evidence that mastering recursion is essential to understanding and exploiting computation and in understanding the role of computational models in studying natural phenomena.

Recursion has reinforced for us the idea of proving that a program operates as intended. The natural connection between recursion and mathematical induction is essential. For everyday programming, our interest in correctness is to save time and energy tracking down bugs. In modern applications, security and privacy concerns make correctness an *essential* part of programming. If the programmer cannot be convinced that an application works as intended, how can a user who wants to keep personal data private and secure be so convinced?

Recursion is the last piece in a programming model that served to build much of the computational infrastructure that was developed as computers emerged to take a central role in daily life in the latter part of the 20th century. Programs built from libraries of functions consisting of statements that operate on primitive types of data, conditionals, loops, and function calls (including recursive ones) can solve important problems of all sorts. In the next section, we emphasize this point and review these concepts in the context of a large application. In CHAPTER 3 and in CHAPTER 4, we will examine extensions to these basic ideas that embrace the more expansive style of programming that now dominates the computing landscape.