2.7. RECURSION

Below are the Koch curves of order 0, 1, 2, and 3.

Designing recursive programs is trickier than designing programs with loops, branches, and non-recursive functions. The first step is to include a base case so that we can verify and test that the function works for a simple input, say n = 0. We accomplish this by checking to see if the input value is 0, and if it is, draw one line segment and return immediately. Recursion does not play any role in this part. Now, the difficult part is to express drawing a Koch curve of order n in terms of drawing one or more Koch curves of order n-1. The code below follows the formula proscribed in the definition of the Koch curve. For this step we assuming that our program correctly draws the Koch curve of order n-1 (and all other smaller values). This assumption is sometimes referred to as the "leap of faith."

public static void koch(int n, double size) { if (n == 0) StdDraw.goForward(size); else { koch(n-1, size); StdDraw.rotate(60); koch(n-1, size); StdDraw.rotate(-120); koch(n-1, size); StdDraw.rotate(60); koch(n-1, size); } }

To see why this function works, observe that if n = 0, the function draws a single line. When n = 1, we must verify that it draws a Koch curve of order 1. This is so by plugging n = 1 into the crucial step and remembering that the function already correctly computes an order 0 Koch curve. Now, we can argue that if n = 2, it will draw a Koch curve of order 2. This is so because we can plug n = 2 into the crucial reduction step and recall that we just argued that the function correctly draws a Koch curve of order 1. Repeating the same argument, we can see that the function correctly draws a Koch curve of order 3, 4, 5, and so on. The mathematically inclined reader will notice that this mimics the rules of a powerful proof technique known as mathematical induction and proves that the program works for any positive value of n. (See Appendix XYZ.)

The Koch snowflake of order n consists of three copies of the Koch curve of over n. We draw the three Koch curves one after the other, but rotate 120° clockwise in between. Below are the Koch snowflakes of order 0, 1, 2, and 3.

Program Koch.java reads in a command line parameter N and plots an order N Koch snowflake using our graphics library. It uses some high school geometry to calculate what size to draw the line segments and where to start drawing.

Historical context: In 1872 Karl Weierstrass made the shocking discovery a function that is everywhere continuous but nowhere differentiable. Later this would become one of the characteristic properties of fractals. Helge von Koch wanted to find a less abstract example. In 1904, von Koch described the geometric construction, which we now refer to as the Koch curve. Von Koch proved that, in the limit, the Koch snowflake is a curve of infinite length, but it does not not have a tangent at any point. From this, he proved that there exist continuous functions f(t) and g(t) such that the Koch snowflake is (f(t), g(t)) for 0 &;le t ≤ 1, but f(t) and g(t) are nowhere differentiable.

Towers of Hanoi.

In the great temple at Benares, says he, beneath the dome which marks the centre of the world, rests a brass plate in which are fixed three diamond needles, each a cubit high and as thick as the body of a bee. On one of these needles, at the creation, God placed sixty-four discs of pure gold, the largest disc resting on the brass plate, and the others getting smaller and smaller up to the top one. This is the Tower of Bramah. Day and night unceasingly the priests transfer the discs from one diamond needle to another according to the fixed and immutable laws of Bramah, which require that the priest on duty must not move more than one disc at a time and that he must place this disc on a needle so that there is no smaller disc below it. When the sixty-four discs shall have been thus transferred from the needle on which at the creation God placed them to one of the other needles, tower, temple, and Brahmins alike will crumble into dust, and with a thunderclap the world will vanish.

We use a recursive solution which is based on the following idea: To move N disks from pole A to pole C, we first move the top N-1 disks from pole A to pole B, then move disk N to pole C, then move the N-1 disks from B to C (onto disk N).

Program Hanoi.java is a direct implementation of this strategy. It reads in a command line parameter N and prints out the solution to the Towers of Hanoi problem on N discs. The function hanoi moves n disks from the from pole, to the to pole, using the temp pole as temporary storage.

public static void hanoi(int n, String from, String temp, String to) { if (n == 0) return; hanoi(n-1, from, to, temp); System.out.println("Move disc " + n + " from " + from + " to " + to); hanoi(n-1, temp, from, to); }

The figure below illustrates the sequence of moves produced by our algorithm when N = 5 discs.

Several underlying patterns are evident, which we now consider in detail.

• First, the recursive structure of this solution immediately tells us the number of moves that the solution requires. (2^N - 1). If the monks are moving disks at the rate of one per second, it will take at least 348 centuries for them to finish the 40 disc problem assuming that they do not make a mistake. The end of the world is likely to be even further off than that because those monks presumably never have had the benefit of being able to use Program Hanoi.java, and might not be able to figure out so quickly which disk to move next. We now consider an analysis of the method that leads to a simple (nonrecursive) method that makes the decision easy. While we may not wish to let the monks in on the secret, it is relevant to numerous important practical algorithms.
• Every other move involves the smallest disc, and it always moves in the same direction (left if n is even/odd, and right if n is odd/even). When the algorithm isn't moving the smallest disc, there is only one legal move, and the algorithm takes it. Thus, analysis of our recursive algorithm yields a simple iterative algorithm. Perhaps our monks do know this secret, because it is hard to imagine how they might be deciding which moves to make otherwise.

Brownian motion.

• Maintain an interval with endpoints (x0, y0) and (x1, y1).

• Divide the interval in half.

• Randomly displacement the midpoint to (x_mid, y_mid) where x_mid = (x0 + x1)/2 and y_mid = (y0 + y1)/2 + Δ and Δ is chosen at random to be a value from the Gaussian distribution with mean 0 and variance (Δ_n)² = σ² / 2ⁿ⁺¹ in level n.

• Recur on the left and right intervals.

     

We can create a fractional Brownian motion by changing the formula we use to update the variance. (Δ_n)² = σ² / (2ⁿ)^2H (1 - 2^{2H - 2}). The Hurst exponent H controls the roughness of the curve. When H = 1/2, it corresponds to regular Brownian motion; when 0

     

Plasma cloud.

• Divide the square into four quadrants and draw four plasma clouds of size s/2 in each of the four quadrants.

• The color of each corner is the convex combination (average) of the others. But we randomly perturb the color of the center point by a displacement. At level i we choose the displacement by generating a random value from the Gaussian distribution with mean 0 and standard deviation 2^(-i).

Here's an 800-by-800 example. Here's a reference, including a simple 1D version. Note: some visual artifacts are noticeable parallel to the x and y axes. Not quite fractional Brownian motion. Use square-diamond method instead.

This method can also used to produce synthetic clouds (by choosing different starting colors) and terrain (by using the color value as the altitude). Variants of this scheme are widely used in the entertainment industry.

Hilbert space-filling curve.

Composing a recursive program to generate the Hilbert curve is a challenging task. Indeed it is a testament to the power of recursion that we can write such a short program to do so. We accomplish the goal by writing two mutually recursive functions hilbert0 and hilbert1. The first functions draws a Hilbert curve, and the second draws the mirror image of a Hilbert curve. Each function calls itself twice recursively, and the other function twice. Program Hilbert.java takes a command line parameter N and draws the order N Hilbert curve using our graphics library.

In addition to its aesthetic beauty, the Hilbert curve has many properties that make it useful for scientific computing. In certain parallel computing applications, scientists need to map the integers 1 to N² to an N-by-N grid of processors in the plane in in such a way that nearby integers are mapped to nearby gridpoints in the plane, or vice versa. Indexing schemes based on Hilbert curves and other space-filling curves are widely used. Each processor handles one point. If the communication cost is primarily between neighboring points, then it is desirable to map them to nearby gridpoints to minimize network contention and latency. The communication cost depends on the Manhattan distance between the processor gridpoints. Using the Hilbert ordering, points i and j are at most 3 * sqrt(|i-j|) links apart. With the standard row major ordering, points 1 and N are a distance N-1 apart; with the Hilbert ordering, they are at most 3 sqrt(N-1) apart. Worst-case useful to remove bottlenecks in parallel computing. Points that are adjacent in time (according to Hilbert scan) are adjacent spatially. This property is useful in image processing (e.g., dithering). More important applications to scientific computing for load balancing of parallel processors. Here objects near in space are placed in near primary or secondary storage. Often used in N-body tree codes, also in adaptive mesh refinement strategies for solving systems of PDEs, e.g., for geophysical fluid dynamics.

Dragon curve. Program Dragon.java reads in a command line parameter N and plots the order N dragon curve using turtle graphics. The dragon curve was first discovered by three NASA physicists (John E. Heighway, Bruce A. Banks, and William G. Harter) and later popularized by Martin Gardner in Scientific American (March and April 1967) and Michael Crichton in Jurassic Park.

This is a sophisticated program that uses two mutually recursive functions. Explain how it works here.

Program SequentialDragon.java is an iterative version of the dragon curve. It is a hacker's paradise. Explain how it works here.

A spectacularly inefficient program. Program SlowFibonacci.java takes a command line parameter N and prints out the first N Fibonacci numbers. It is spectacularly inefficient. To see why, consider what the function does to compute F(8) = 21. It first computes F(7) = 13 and F(6) = 8. To compute F(7), it recursively computes F(6) and F(5) = 5. It's important to observe that F(6) is computed twice - the result is not stored so it must be recomputed from scratch. This does not see so bad, but things rapidly get worse. F(5) is computed three times; F(4) is computed five times; and F(3) is computed eight times, and so forth. The figure below shows the complete recursion tree when computing F(8).

In general F(n) is computed F(N-n) times. As an example, to compute F(200), F(1) is computed F(199) > 1.73 * 10⁴¹ times! No imaginable computer will ever be able to do this many calculations.

Recursion vs. iteration. Are there situations when we need recursion? No, any recursive function can be replaced by an iterative counterpart. In Section XYZ, we'll explain how a compiler implements a function call by using a data structure called a pushdown stacks. Conversely, we can convert any iterative program to one that uses recursion instead.

Lessons

1. Use a base case to avoid an infinite loop.
2. Methods can call other methods including themselves.
3. It's easy to write spectacularly inefficient recursive programs if you're not careful.
4. Recursion is an alternate to for and while loops for performing repetitive computations.
5. Recursive functions are especially useful when either the underlying data structure (binary trees, Unix directories) or the underlying algorithmic paradigm (divide-and-conquer) are naturally self-referential.

Q + A

Q. What does the following error message mean?

Exception in thread "main" java.lang.StackOverflowError

A. Typically, this means that your recursive function has no base case. The system makes too many function calls and runs out of memory.

Q. Can main be recursive?

A. Absolutely. It takes as input an array of strings.

Exercises

1. What happens if you run Factorial.java with a command line argument that is negative?
2. What happens if you run Factorial.java with a command line argument that is large, say 17?
3. Is there any difference in what the following two functions do?

   public static boolean factorial(int n) { if (n == 0) return 1; else return n * factorial(n-1); }

   public static boolean factorial(int n) { if (n == 0) return 1; return n * factorial(n-1); }

4. Does Euclid.java still work if the first input is greater than the second argument?
5. Does Euclid.java still work if the inputs can be negative? If not, fix it. Hint: Recall that % can return a negative integer if the first input is negative. When calling the function, take the absolute value of both inputs.
6. Given four positive integers a, b, c, and d, explains what gcd(gcd(a, b), gcd(c, d)) computes.
7. Explain in terms of integers and divisors what the following Euclid-like function does.

   public static boolean gcdlike(int p, int q) { if (q == 0) return (p == 1); else return gcdlike(q, p % q); }

8. Write a recursive program GoldenRatio.java that takes an integer input N and computes an approximation to the golden ratio using the following recursive formula.

   f(N) = 1 if N = 0 = 1 + 1 / f(N-1) if N > 0

9. Redo the previous exercise but do not use recursion.
10. Consider the following recursive function.

    public static int mystery(int a, int b) { if (b == 0) return 0; else if (b % 2 == 0) return mystery(a + a, b / 2); else return mystery(a + a, b / 2) + a; }

    What is mystery(2, 25)? mystery(3, 35)? Given positive integers a and b, describe what mystery(a, b) computes. Answer: 50, 105, product of a and b.

11. Consider the following recursive function.

    public static int mystery(int a, int b) { if (b == 0) return 1; else if (b % 2 == 0) return mystery(a * a, b / 2); else return mystery(a * a, b / 2) * a; }

    What is mystery(2, 4)? mystery(3, 5)? Given positive integers a and b, describe what mystery(a, b) computes.

12. Repeat the previous exercise, but replace the return 1 with return 0.
13. Consider the following recursive function. What is mystery(1, 7)?

    public static int mystery(int a, int b) { if (0 == b) return 0; else return a + f(a, b-1); }

    Answer: mystery(1, 7) = 1 + mystery(1, 6) = 1 + (1 + mystery(1, 5)) = ... 7 + mystery(1, 0) = 7.

14. Will the function in the previous exercise terminate for every pair of integers a and b between between 0 and 100? Give a high level description of what mystery(a, b) returns, given integers a and b between 0 and 100.

    Answer: Yes, the base case is b = 0. Successive recursive calls reduce b by 1, driving it toward the base case. The function mystery(a, b) returns a * b. Mathematically inclined students can prove this fact via induction using the identity ab = a + a(b-1).

15. Consider the following function. What does mystery(0, 8) do?

    public static void mystery(int a, int b) { if (a != b) { int m = (a + b) / 2; mystery(a, m); System.out.println(m); mystery(m, b); } }

    Answer: infinite loop.
16. Consider the following function. What does mystery(0, 8) do?

    public static void mystery(int a, int b) { if (a != b) { int m = (a + b) / 2; mystery(a, m - 1); System.out.println(m); mystery(m + 1, b); } }

    Answer: stack overflow.
17. Repeat the previous exercise, but replace if (a != b) with if (a <= b).
18. What does mystery(0, 8) do?

    public static int mystery(int a, int b) { if (a == b) System.out.println(a); else { int m1 = (a + b ) / 2; int m2 = (a + b + 1) / 2; mystery(a, m1); mystery(m2, b); } }

19. What does the following function compute?

    public static int f(int n) { if (n == 0) return 0; if (n == 1) return 1; if (n == 2) return 1; return 2*f(n-2) + f(n-3);

20. Write a program Fibonacci.java that takes a command line parameter N and prints out the first N Fibonacci numbers using the following alternate definition:

    F(n) = 1 if n = 1 or n = 2 = F((n+1)/2)2 + F((n-1)/2)2 if n is odd = F(n/2 + 1)2 - F(n/2 - 1)2 if n is even

    What is the biggest Fibonacci number you can compute in under a minute using this definition?

21. Write a program that takes a command line parameter N and prints out the first N Fibonacci numbers using the following method proposed by Dijkstra:

    F(0) = 0 F(1) = 1 F(2n-1) = F(n-1)^2 + F(n)^2 F(2n) = (2F(n-1) + F(n)) * F(n)

22. Prove by mathematical induction that the alternate definitions of the Fibonacci function given in the previous two exercises are equivalent to the original definition.
23. Write a recursive program Ruler.java to plot the subdivisions of a ruler using turtle graphics.
24. Write a program Pell.java that takes a command line parameter N and prints out the first N Pell numbers: p₀ = 0, p₁ = 1, and for n >= 2, p_n = 2 p_n-1 + p_n-2. Print out the ratio of successive terms and compare to 1 + sqrt(2).
25. Consider the following function from program Recursion.java:

    public static void mystery(int n) { if (n == 0 || n == 1) return; mystery(n-2); System.out.println(n); mystery(n-1); }

    What does mystery(6) print out? Hint: first figure out what mystery(2), mystery(3), and so forth print out.

26. What would happen in the previous exercise if the base case was replaced with the following statement?

    if (n == 0) return;

27. Consider the following function. What does mystery(6) print out?

    public static void mystery(int n) { if (n > 0) { System.out.println(n); mystery(n-2); mystery(n-3); System.out.println(n); } }

28. Consider the following function. What does mystery(6) return?

    public static String mystery(int n) { if (n <= 0) return "" ; return mystery(n-3) + n + mystery(n-2) + n; }

29. Consider the following recursive functions.

    public static int square(int n) { if (n == 0) return 0; return square(n-1) + 2*n - 1; } public static int cube(int n) { if (n == 0) return 0; return cube(n-1) + 3*(square(n)) - 3*n + 1; }

    What is square(5)? cube(5)? cube(123)?

30. Consider the following pair of mutually recursive functions. What does g(g(2)) evaluate to?

    public static int f(int n) { public static int g(int n) { if (n == 0) return 0; if (n == 0) return 0; return f(n-1) + g(n-1); return g(n-1) + f(n); } }

31. The anti-Koch snowflake is generated exactly like the Koch snowflake, except that clockwise and counterclockwise are interchanged. Write a program AntiKoch.java that takes a command line parameter N and plots the anti-Koch snowflake of order N using Turtle graphics.

32. A randomized Koch snowflake is generated exactly like the Koch snowflake, except that we flip a coin to generate the clockwise and counterclockwise direction at each step.
33. Write program to verify that (for small values of n) the sum of the cubes of the first n Fibonacci numbers F(0)^3 + F(1)^3 + ... + F(n)^3 equals (F(3n+4) + (-1)^n * 6 * f(n-1)) / 10, where F(0) = 1, F(1) = 1, F(2) = 2, and so forth.

Creative Exercises

1. Binary representation. Write a program BinaryConverter.java that takes a command line input N (in decimal), and prints out its binary representation. Recall, in section XYZ, we used the method of casting out powers of 2. Here, we uses the following simpler method: repeatedly divide 2 into N and read the remainders backwards. It would be easy to write a while loop to carry out this computation and print the bits in the wrong order. Use recursion to print the bits in the correct order.
2. Transformations by increment and unfolding. Given two integers a ≤ b, write a program Sequence.java that transforms a into b by a minimum sequence of increment (add 1) and unfolding (multiply by 2) operations. For example,

   % java Sequence 5 23 23 = ((5 * 2 + 1) * 2 + 1) % java Sequence 11 113 113 = ((((11 + 1) + 1) + 1) * 2 * 2 * 2 + 1)

3. Infix expression evaluator. Infix expression evaluator with recursion.
4. Hadamard matrix. Write a recursive program Hadamard.java that takes a command line input n and plots an N-by-N Hadamard pattern where N = 2ⁿ. Do not use an array. A 1-by-1 Hadamard pattern is a single black square. In general a 2N-by-2N Hadamard pattern is obtained by aligning 4 copies of the N-by-N pattern in the form of a 2-by-2 grid, and then inverting the colors of all the squares in the lower right N-by-N copy. The N-by-N Hadamard H(N) matrix is a boolean matrix with the remarkable property that any two rows differ in exactly N/2 bits. This property makes it useful for designing error-correcting codes. Here are the first few Hadamard matrices.

5. Permutations. Write a program Permutations.java that take a command line parameter N and prints out all N! permutations of N items. A permutation of N elements is one of the N! possible orderings of the elements. As an example, when N = 3 you should get the following output. Do not worry about the order in which you enumerate them.

   bca cba cab acb bac abc

6. Permutations. Write a program Permutations.java that take a command line parameter N and prints out all N! permutations of N items in lexicographic order.

   abc acb bac bca cab cba

7. Permutations of size k. Modify Permutations.java to Perm.java so that it takes two command line parameters N and k, and prints out all P(n, k) = N! / (N-k)! permutations that contain exactly k of the N elements. Below is the desired output when k = 2 and N = 4. You need not print them out in alphabetical order.

   ab ac ad ba bc bd ca cb cd da db dc

8. Combinations. Write a program Combinations.java that take two command line parameter N and k, and prints out all C(N, k) = N! / (k! * (N-k)!) combinations of size k. A combination is a subset of the N elements, independent of order. As an example, when N = 3 you should get the following output.

   abc abd abe acd ace ade bcd bce bde cde

   Alternate solution: Combinations2.java.
9. Hamming distance. The Hamming distance between two bit strings of length N is equal to the number of bits in which the two strings differ. Write a program that reads in an integer k and a bit string s from the command line, and prints out all bit strings that having Hamming distance at most k from s. For example if k = 2 and s = 0000 then your program should print out 0011, 0101, 0110, 1001, 1010, and 1100. Hint: choose k of the N bits in s to flip.
10. 8 queens problem. In this exercise, you will solve the classic 8-queens problem: place 8 queens on an 8x8 chess board so that no two queens are in the same row, column, or diagonal. There are 8! = 40,320 ways in which no two queens are placed in the same row or column. Any permutation p[] of the integers 0 to 7 gives such a placement: put queen i in row i, column p[i]. Modify Permutations.java to solve the 8 queens problem. You will need to add a test to check whether any pair of queens in a given permutation are on a common diagonal. Your program Queens.java should take one command line parameter N and enumerate all solutions to the N-queens problem by drawing the location of the queens in ASCII like the two solutions below.

    * * * Q * * * * * * * * Q * * * * Q * * * * * * * Q * * * * * * * * * * * * Q * * * * Q * * * * * * Q * * * * * * * * * * * Q * * * * * * Q * * * * Q * * * * * * * * * * * * Q * * * * * * * Q * * * * Q * * * * * * * * Q * * Q * * * * * * * Q * * * * * * *

11. Faster 8 queens solver. The program Queens.java works for N = 8 but is excessively slow for N = 25. Modify it so that it runs in a reasonable amount of time for N = 25 (around 1 second) by short-circuiting the enumeration to avoid further exploring permutations that already have two queens in conflicting positions. Name your program QueensPruner.java.
12. A4 paper. The width-to-height ratio of paper in the ISO format is sqrt(2) to 1. Format A0 has an area of 1 square meter. Format A1 is A0 cut with a vertical line into two equal halves, A2 is A1 cut with a horizontal line into in two halves, and so on. Write a program that takes a command line integer N and cuts a sheet of A0 paper into 2^N pieces as in the picture below.
13. Euclid's algorithm and π. The probability that two numbers chosen from a large random set of numbers have no common factors (other than 1) is 6 / π². Use this idea to estimate π. Robert Matthews use the same idea to estimate π by taken the set of numbers to be a function of the positions of stars in the sky.
14. Perfect maze. Generate a perfect maze like this one
    

    Write a program Maze.java that takes a command line parameter N, and generates a random N-by-N perfect maze. A maze is perfect if it has exactly one path between every pair of points in the maze, i.e., no inaccessible locations, no cycles, and no open spaces. Here's a nice algorithm to generate such mazes. Consider an N-by-N grid of cells, each of which initially has a wall between it and its four neighboring cells. For each cell (x, y), maintain a variable north[x][y] that is true if there is wall separating (x, y) and (x, y + 1). We have analogous variables east[x][y], south[x][y], and west[x][y] for the corresponding walls. Note that if there is a wall to the north of (x, y) then north[x][y] = south[x][y+1] = true. Construct the maze by knocking down some of the walls as follows:

    1. Start at the lower level cell (1, 1).
    2. Find a neighbor at random that you haven't yet been to.
    3. If you find one, move there, knocking down the wall. If you don't find one, go back to the previous cell.
    4. Repeat steps ii. and iii. until you've been to every cell in the grid.

    Hint: maintain an (N+2)-by-(N+2) grid of cells to avoid tedious special cases.

15. Getting out of the maze. Given an N-by-N maze (like the one created in the previous exercise), write a program to find a path from the start cell (1, 1) to the finish cell (N, N), if it exists. To find a solution to the maze, run the following algorithm, starting from (1, 1) and stopping if we reach cell (N, N).

    explore(x, y) ------------- - Mark the current cell (x, y) as "visited." - If no wall to north and unvisited, then explore(x, y+1). - If no wall to east and unvisited, then explore(x+1, y). - If no wall to south and unvisited, then explore(x, y-1). - If no wall to west and unvisited, then explore(x-1, y).

16. Towers of Hanoi variant I. Consider the following variant of the Towers of Hanoi problem. There are 2N discs of increasing size stored on three poles. Initially all of the discs with odd size (1, 3, ..., 2N-1) are piled on pole A from top to bottom in increasing order of size; all of the discs with even size (2, 4, ..., 2N) are piled on pole C. The goal is to move the odd discs to pole C and the even discs to pole A while obeying the same rules as in the original Towers of Hanoi problem.
    1. Is there an algorithm to solve it? If so, write the algorithm and analyze the number of disk moves.
    2. Otherwise, argue that it is not possible.
17. Towers of Hanoi variant II. (Knuth-Graham and Pathashnik) Solve the original Towers of Hanoi problem, but with the extra restriction that you are not allowed to directly transfer a disk from A to C. How many moves does it take to solve a problem with N disks? Hint: move N-1 smallest disks from A to C recursively (without any direct A to C moves), move disk N from A to B, move N-1 smallest disks from C to A (without any direct A to C moves), move disk N from B to C, and move N-1 smallest disks from A to C recursively (without any direct A to C moves).
18. Towers of Hanoi variant III. Repeat the previous question but disallow both A to C and C to A moves. That is, each move must involve pole B.
19. Towers of Hanoi with 4 pegs. Suppose that you have a fourth peg. What is the least number of moves needed to transfer a stack of 8 disks from the leftmost peg to the rightmost peg? Answer. Finding the shortest such solution in general has remained an open problem for over a hundred years.
20. Pancake flipping. You have a stack of N pancakes of varying sizes on a griddle. Your goal is to re-arrange the stack in descending order so that the largest pancake is on the bottom and the smallest one is on top. You are only permitted to flip the top k pancakes, thereby reversing their order. Devise a scheme to arrange the pancakes in the proper order by using at most 2N - 3 flips. You can try out strategies here.
21. Recursive squares. Write a program to produce each of the following recursive patterns. The ratio of the sizes of the squares is 2.2. To draw a shaded square, draw a black square and then a gray square of slightly smaller size.
    1.  
    2.  
    3.  
    4.  
22. Colorful recursive squares. (Cole Forest) Add some color to the recursive squares in the previous exercise.

23. Koch snowflake with rainbow of colors. Modify Koch.java so that it plots the Koch snowflake in a continuous spectrum of colors from red, to orange, yellow, green, blue, and indigo, and violet. Animate the results so that you can visualize the turtle tracing out the desired path. Name your program KochRainbow.java.

24. Recursive graphics.
    1. H-tree.
    2. Gosper island.
    3. Minkowski sausage.
    4. Cesaro broken square.
25. Sierpinski gasket. Write a program to draw the Sierpinski gasket. First, draw the outer equilateral triangle using StdDraw.rotate and StdDraw.forward - it is not part of the recursive pattern. An order n Sierpinski gasket with "bottom center" (x, y) and side length s is (i) an equilateral triangle with bottom corner at (x, y), (ii) three order n-1 Sierpinski gaskets of side length s/2 centered at (x - s/2, y), (x + s/2, y), and (x, y + sqrt(3)/2). To draw a filled in equilateral triangle, add another spot method to StdDraw.java using Graphics.fillPolygon.

26. More recursive graphics. Write a program to produce each of the following recursive patterns.
    1. Levy tapestry.
    2. Fudgeflake.
27. Recursive graphics (hard). Write a program to produce each of the following recursive patterns without lifting the pen or tracing over the same line segment more than once.
    1. Sierpinski arrowhead.
    2. Sierpinski curve.
28. Towers of Hanoi animation. Write a program AnimatedHanoi.java that produces a graphical simulation of the solution to the Towers of Hanoi problem from Hanoi.java. Use turtle graphics for the animation. Think carefully about what data structures you will need to record which discs are on which poles.
29. McCarthy's 91 function. Consider McCarthy's 91 function:

    public static int mcCarthy(int n){ if (n > 100) return n - 10; else return mcCarthy(mcCarthy(n+11)); }

    1. Determine the value of mcCarthy(50) without using a computer.
    2. Is the function defined for all positive integers n, i.e., does the recursive definition "bottom out" for all integers n?
30. Another tricky recursive function. Consider the following recursive function. What is f(0)?

    public static int f(int x) { if (x > 1000) return x - 4; else return f(f(x+5)); }

31. Another sequence. Consider the following recursive function. f(n) = n - f(f(n-1)) for n > 0 and f(0) = 0.
32. Gray codes. See exercises in section 5.1.

Copyright © 2004, Robert Sedgewick and Kevin Wayne. All rights reserved.