4. Recursion

Download Project Zip | Submit to TigerFile

Goals

• To gain practice designing and implementing recursive functions.
• To write a program that plots a Sierpinski triangle.
• To design and develop a program that plots a recursive pattern of your own design.
• To understand the trade-offs between recursive and dynamic programming approaches to solving problems.

Getting Started

• Make sure you understand the lecture materials and the precept exercises before proceeding. Refer to the lecture and precept examples while you are coding.

• Download and expand the zip file, which will create the folder recursion. We recommend this folder be placed in a cos126 folder.

• You may not call library functions except those in

  • java.lang such as Integer.parseInt(), etc.
  • StdDraw

• You may not use Java features that have not yet been introduced in the course (such as objects).

• Use the StdRandom API instead of Math.random()

Background

Read Sections 2.3 and 4.1 in the textbook. You may also find it instructive to work through the precept exercises. You should also familiarize yourself with the StdDraw API.

Delannoy numbers (brute force).

Write a program DelannoyBrute.java that takes two integer command-line arguments \(m\) and \(n\) and computes the corresponding Delannoy number. The Delannoy number \(D(m, n)\) is the number of paths from \((0,0)\) to \((m, n)\) in a rectangular grid using only single steps north, east, and northeast. For example, \(D(2, 2) = 13\) because these are the \(13\) possible Delannoy paths:

Implement a recursive function count() to compute \(D(m,n)\) using the following recurrence relation:

$$ \displaystyle D(m, n) \; = \; \begin{cases} \;\; 1 & \text{if } m = 0 \\[.5em] \;\; 1 & \text{if } n = 0 \\[.5em] \;\; D(m-1, n) + D(m-1, n-1) + D(m, n-1) & \text{otherwise} \end{cases} $$ To do so, organize your program according to the following public API:

public class DelannoyBrute {

    // Returns the Delannoy number D(m, n).
    public static long count(int m, int n)

    // Takes two integer command-line arguments m and n and prints D(m, n).
    public static void main(String[] args)
}

As you will see, this approach is hopelessly slow, even for moderately small values of \(m\) and \(n\).

java-introcs DelannoyBrute 2 2
13

java-introcs DelannoyBrute 3 2
25

java-introcs DelannoyBrute 2 3
25

java-introcs DelannoyBrute 3 3
63

java-introcs DelannoyBrute 20 20
[takes too long]

Notes:

• You may assume that \(m\) and \(n\) are non-negative integers.
• You must not add public methods to the API; however, you may add private methods (which are accessible only in the class in which they are declared).

Delannoy numbers arise in combinatorics and computational biology. For example, it is the number of global alignments of two strings of lengths \(m\) and \(n\).

Sierpinski Triangle

The Sierpinski triangle is an example of a fractal pattern like the H-tree pattern from Section 2.3 of the textbook.

Order 1	Order 2	Order 3
Order 4	Order 5	Order 6

The Polish mathematician Wacław Sierpiński described the pattern in 1915, but it has appeared in Italian art since the 13th century. Though the Sierpinski triangle looks complex, it can be generated with a short recursive function.

Your primary task is to write a recursive function sierpinski() that plots a Sierpinski triangle of order n to standard drawing. Think recursively: sierpinski() should draw one filled equilateral triangle (pointed downwards) and then call itself recursively three times (with an appropriate stopping condition). It should draw one (1) filled triangle for n = 1; four (4) filled triangles for n = 2; and thirteen (13) filled triangles for n = 3; and so forth.

When writing your program, exercise modular design by organizing it into four functions, as specified in the following API:

public class Sierpinski {

    // Height of an equilateral triangle with the specified side length.
    public static double height(double length)

    // Draws a filled equilateral triangle with the specified side length
    // whose bottom vertex is (x, y).
    public static void filledTriangle(double x, double y, double length)

    // Draws a Sierpinski triangle of order n, such that the largest filled
    // triangle has the specified side length and bottom vertex (x, y).
    public static void sierpinski(int n, double x, double y, double length)

    // Takes an integer command-line argument n;
    // draws the outline of an upwards equilateral triangle of length 1
    // whose bottom-left vertex is (0, 0) and bottom-right vertex is (1, 0);
    // and draws a Sierpinski triangle of order n that fits inside the outline.
    public static void main(String[] args)

}

The formula for the height of an equilateral triangle of side length \( s \) is \( h = s \times \frac{\sqrt{3}}{2} \).

Here is the layout of the initial equilateral triangle. The top vertex lies at \( (\frac{1}{2},\frac {\sqrt{3}}{2}) \).

Here is the layout of an inverted equilateral triangle.

Requirements

1. The program must take an integer command-line argument n.
2. To draw a filled equilateral triangle, you should call the method StdDraw.filledPolygon() with appropriate arguments.
3. To draw an unfilled equilateral triangle, you should call the method StdDraw.polygon() with appropriate arguments.
4. You must not call StdDraw.save(), StdDraw.setCanvasSize(), StdDraw.setXscale(), StdDraw.setYscale(), or StdDraw.setScale(). These method calls interfere with grading.
5. You may use only StdDraw.BLACK to draw the outline triangle and the filled triangles.

Possible Progress Steps

We provide some additional instructions below. Click on the ► icon to expand some possible progress steps or you may try to solve Sierpinski without them. It is up to you!

java-introcs Sierpinski 0
[no output]

java-introcs Sierpinski 1
1

java-introcs Sierpinski 2
2
1
1
1

java-introcs Sierpinski 3
3
2 1 1 1
2 1 1 1
2 1 1 1

java-introcs Sierpinski 4
4
3 2 1 1 1 2 1 1 1 2 1 1 1
3 2 1 1 1 2 1 1 1 2 1 1 1
3 2 1 1 1 2 1 1 1 2 1 1 1

java-introcs Sierpinski 5
5
4 3 2 1 1 1 2 1 1 1 2 1 1 1
3 2 1 1 1 2 1 1 1 2 1 1 1
3 2 1 1 1 2 1 1 1 2 1 1 1
4 3 2 1 1 1 2 1 1 1 2 1 1 1
3 2 1 1 1 2 1 1 1 2 1 1 1
3 2 1 1 1 2 1 1 1 2 1 1 1
4 3 2 1 1 1 2 1 1 1 2 1 1 1
3 2 1 1 1 2 1 1 1 2 1 1 1
3 2 1 1 1 2 1 1 1 2 1 1 1

java-introcs Sierpinski 0
[no output]

java-introcs Sierpinski 1
1 0.5

java-introcs Sierpinski 2
2 0.5
1 0.25
1 0.25
1 0.25

java-introcs Sierpinski 3
3 0.5
2 0.25  1 0.125  1 0.125  1 0.125
2 0.25  1 0.125  1 0.125  1 0.125
2 0.25  1 0.125  1 0.125  1 0.125

java-introcs Sierpinski 4
4 0.5
3 0.25  2 0.125  1 0.0625  1 0.0625  1 0.0625
2 0.125  1 0.0625  1 0.0625  1 0.0625
2 0.125  1 0.0625  1 0.0625  1 0.0625
3 0.25  2 0.125  1 0.0625  1 0.0625  1 0.0625
2 0.125  1 0.0625  1 0.0625  1 0.0625
2 0.125  1 0.0625  1 0.0625  1 0.0625
3 0.25  2 0.125  1 0.0625  1 0.0625  1 0.0625
2 0.125  1 0.0625  1 0.0625  1 0.0625
2 0.125  1 0.0625  1 0.0625  1 0.0625

Testing

Below are the target Sierpinski triangles for different values of n.

java-introcs Sierpinski 1

java-introcs Sierpinski 2

java-introcs Sierpinski 3

Create Your Own Art

Art.java

In this part you will create a program Art.java that produces a recursive drawing of your own design. This part is meant to be fun, but here are some guidelines in case you’re not so artistic.

A very good approach is to first choose a self-referential pattern as a target output. Check out the graphics exercises in Section 2.3. Here are some of our favorite student submissions from a previous year. See also the Famous Fractals in Fractals Unleashed for some ideas. Here is a list of fractals, by Hausdorff dimension. Some pictures are harder to generate than others (and some require trigonometry).

Requirements

1. Art.java must take one (1) integer command-line argument n that controls the depth of recursion.
2. Your drawing must stay within the drawing window when n is between 1 and 6 inclusive. (The autograder will not test values of n outside of this range.)
3. You may not change the size of the drawing window (but you may change the scale). Do not add sound.
4. Your drawing can be a geometric pattern, a random construction, or anything else that takes advantage of recursive functions.
5. Optionally, you may use the Transform2D library you implemented in precept. You may also define additional geometric transforms in Art.java, such as sheer, reflect across the \(x\)- or \(y\)- axis, or rotate about an arbitrary point (as opposed to the origin).
6. Your program must be organized into at least three separate functions, including main(). All functions except main() must be private.
7. For full credit, Art.java must not be something that could be easily rewritten to use loops in place of recursion, and some aspects of the recursive function-call tree (or how parameters or overlapping are used) must be distinct from the in-class examples (HTree, NestedCircles, etc.). You must do at least two of the following to get full credit on Art.java (and doing more may yield a small amount of extra credit):
   • call one or more Transform2D methods
   • use different parameters than in examples: f(n, x, y, size)
   • use different StdDraw methods than in examples (e.g., ellipses, arcs, text; take a look at the StdDraw API)
   • have non-constant number of recursive calls per level (e.g., conditional recursion)
   • have mutually recursive methods
   • have multiple recursive methods
   • use recursion that doesn’t always recur from level n to level n-1
   • draw between recursive calls, not just before or after all recursive calls
   • use recursive level for secondary purpose (e.g., level dictates color)
8. Contrast this with the examples HTree, Sierpinski, and NestedCircles, which have very similar structures to one another.
9. You will also lose points if your artwork can be created just as easily without recursion (such as Factorial.java). If the recursive function-call tree for your method is a straight line, it probably falls under this category.
10. You may use GIF, JPG, or PNG files in your artistic creation. If you do, be sure to submit them along with your other files. Make it clear in your readme.txt what part of the design is yours and what part is borrowed from the image file.

FAQ

The API checker says that I need to make my methods private. Use the access modifier private instead of public in the method signature. A public method can be called directly in another class; a private method cannot. The only public method that you should have in Art.java is main().

What will cause me to lose points on the artistic part? We consider two things: the structure of the code and the structure of the recursive function-call tree.

For example, the Quadricross looks very different from the in-class examples, but the code to generate it looks extremely similar to HTree, so it is a bad choice. On the other hand, even though the Sierpinski curve eventually generates something that looks like the Sierpinski triangle, the code is very different (probably including an angle argument in the recursive method), and so it would earn full marks.

Here is an animation we produced using student art:

Delannoy numbers (dynamic programming)

You have now written three recursive programs. This programming exercise demonstrates the efficiency of using a dynamic programming approach to solving a problem.

Write a program DelannoyMemo.java that takes two integer command-line arguments \(m\) and \(n\) and computes the Delannoy number \(D(m, n)\) using dynamic programming.

• Use a private static two-dimensional array with element memo[i][j] storing \(D(i,j)\).
• Review pages 106-111 in your textbook.
• Review FibonnaciMemo.java (from lecture) and PalindromeMemo.java (from precept). Your code DelannoyMemo.java should be structured similarly to these exercises.
• You must not add public methods to the API; however, you may add private methods (which are accessible only in the class in which they are declared).

To do so, organize your program according to the following public API:

public class DelannoyMemo {

    // Returns the Delannoy number D(m, n).
    public static long count(int m, int n)

    // Takes two integer command-line arguments m and n and prints D(m, n).
    public static void main(String[] args)
}

This version should be fast enough to handle larger values of \(m\) and \(n\).

java-introcs DelannoyMemo 2 2
13

java-introcs DelannoyMemo 3 2
25

java-introcs DelannoyMemo 2 3
25

java-introcs DelannoyMemo 3 3
63

java-introcs DelannoyMemo 20 20
260543813797441

Analysis - readme.txt

Provide your answers to the following questions in the readme.txt file.

Conduct the following experiments, where \(m\) and \(n\) are the same:

java-introcs DelannoyBrute 2 2

java-introcs DelannoyBrute 4 4

java-introcs DelannoyBrute 8 8

java-introcs DelannoyBrute 16 16

java-introcs DelannoyMemo 2 2

java-introcs DelannoyMemo 4 4

java-introcs DelannoyMemo 8 8

java-introcs DelannoyMemo 16 16

1. Based your computational experiments, which function runs faster: DelannoyBrute.count() or DelannoyMemo.count() ?

2. Using a mathematical model, what is the estimated order of growth of the running time of DelannoyBrute.count(n, n) as a function of \(n\)?

   \(\Theta(1)\) - constant, \(\Theta(\log n)\) - logarithmic, \(\Theta(n)\) - linear, \(\Theta(n\log n)\) - linearithmic, \(\Theta(n^2)\) - quadratic, \(\Theta(n^3)\) - cubic or \(\Theta(c^n)\) - exponential

3. Empirically analyze DelannoyMemo.count(n, n) using the doubling method. Complete the following table by conducting experiments for n = 3000, 6000, 12000, 24000.

java-introcs -Xss10m  DelannoyMemo 3000 3000

java-introcs -Xss10m  DelannoyMemo 6000 6000

java-introcs -Xss10m  DelannoyMemo 12000 12000

java-introcs -Xss10m  DelannoyMemo 24000 24000

The command-line option -Xss10m in Java is used to set the stack size for each thread. Specifically, -Xss allows you to specify the stack size in bytes, and in this case, 10m indicates a size of 10 megabytes.

4. Based on your empirical analysis, what is the estimated order of growth of the running time of DelannoyMemo.count(n, n) as a function of \(n\)?

   \(\Theta(1)\) - constant, \(\Theta(\log n)\) - logarithmic, \(\Theta(n)\) - linear, \(\Theta(n\log n)\) - linearithmic, \(\Theta(n^2)\) - quadratic, \(\Theta(n^3)\) - cubic or \(\Theta(c^n)\) - exponential

Notes:

• For your empirical analysis, you may observe the result returned by count() will overflow a long data type. However, you can ignore the values returned by count() since they do not impact the order of growth of the implementation.

• Instrument your working version DelannoyMemo.java similarly to how your code was instrumented in precept using System.currentTimeMillis(). Do not submit the instrumented version of DelannoyMemo.java to TigerFile.

• If you receive a message such as Exception in thread "main" java.lang.OutOfMemoryError: Java heap space, try allocating more memory to your Java process. For example:

  java-introcs -Xss50m -Xmx5g DelannoyMemo 24000 24000

The command-line option -Xmx5g in Java is used to specify the maximum heap size for the Java Virtual Machine (JVM). The heap is the area of memory used for dynamic memory allocation in Java. This is where objects created by your application are stored. The -Xmx flag sets the upper limit for the heap memory that the JVM can allocate. In this case, 5g means that the maximum heap size is set to 5 gigabytes.

Submission

• Submit to TigerFile : DelannoyBrute.java, Sierpinski.java, Art.java (and optional image files), DelannoyMemo.java, and completed readme.txt and acknowledgments.txt files.

• Note that, as part of this assignment, we may anonymously publish your art. If you object, please indicate so in your readme.txt when asked. We also reserve the right to pull any art, at any time, for whatever reason; by submitting your assignment, you implicitly agree with this policy.

Grading

Enrichment

Fractals in the wild. Here’s a Sierpinski triangle in polymer clay, a Sierpinski carpet cookie, a fractal pizza, and a Sierpinski hamantaschen.

Fractal dimension (optional diversion). In grade school, you learn that the dimension of a line segment is 1, the dimension of a square is 2, and the dimension of a cube is 3. But you probably didn’t learn what is really meant by the term dimension. How can we express what it means mathematically or computationally? Formally, we can define the Hausdorff dimension or similarity dimension of a self-similar figure by partitioning the figure into a number of self-similar pieces of smaller size. We define the dimension to be the \(\log\) (# self similar pieces) / \(\log\) (scaling factor in each spatial direction). For example, we can decompose the unit square into four smaller squares, each of side length 1/2; or we can decompose it into 25 squares, each of side length 1/5. Here, the number of self-similar pieces is 4 (or 25) and the scaling factor is 2 (or 5). Thus, the dimension of a square is 2, since \(\log (4) / \log(2) = \log (25) / \log (5) = 2\). Furthermore, we can decompose the unit cube into 8 cubes, each of side length 1/2; or we can decompose it into 125 cubes, each of side length 1/5. Therefore, the dimension of a cube is \(\log(8) / \log (2) = \log(125) / \log(5) = 3\).

We can also apply this definition directly to the (set of white points in) Sierpinski triangle. We can decompose the unit Sierpinski triangle into three Sierpinski triangles, each of side length 1/2. Thus, the dimension of a Sierpinski triangle is \(\log (3) / \log (2) ≈ 1.585\). Its dimension is fractional—more than a line segment, but less than a square! With Euclidean geometry, the dimension is always an integer; with fractal geometry, it can be something in between. Fractals are similar to many physical objects; for example, the coastline of Britain resembles a fractal; its fractal dimension has been measured to be approximately 1.25.