Skip to Main Content

Introduction to Computer Science

Computer Science Department

Recursion – 50 course points

This assignment consists of writing a program recursive programs. 

Refer to our Programming Assignments FAQ for instructions on how to install VSCode, how to use the command line and how to submit your assignments.

Start your assignment early.

Looking for Help with Assignments?

Programming

We provide a zip file in Autolab containing Ladder.java and  SierpinskiSquare.java.

Observe the following rules:

  1. DO NOT add any import statements
  2. DO NOT add the project statement
  3. DO NOT change the class name
  4. DO NOT change the headers of ANY of the given methods
  5. DO NOT add any new class fields
  6. DO NOT use System.exit()
  7. ONLY print the result as specified by each problem. Observe the examples’ output, display only what the problem is asking for.
    1. DO NOT print other messages, follow the examples for each problem.

Ladder (20 points). 

In Ladder.java, write a recursive function createLadder that receives one parameter, an integer n containing the number of levels. The method createLadder returns a string with n levels, following these rules:

  • Odd levels are denoted by |=|\n (rails/step followed by the newline character \n).
    • The rails are separated by ONE assignment character in between.
  • Even levels are denoted by | |\n (rails followed by the newline character \n.
    • The rails are separated by ONE space in between).
  • The topmost level (n = 1) is the end of the ladder and is denoted by |-|\n (rails/dash followed by the newline character \n).
  • Levels are built starting from the bottom and back out at the top (assume n is greater than or equal to 1). 
  • YOUR CODE MUST BE RECURSIVE

Notes:

  1. Use the + operator to append Strings. For example: “aa” + “cc” will create the string “aacc”.
  2. The \n is the newline character. The string “|=|\n” means that “|=|” will be in a line by itself.

Examples:

n = 1
n = 2
n = 3
n = 6

Problem by Kal Pandit and Mary Buist.

Sierpinski (30 points). 

This part of the assignment consists of writing a program that plots a Sierpinski Square, a variation of the commonly known Sierpinski Triangle.

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

The original Sierpinski triangle was created by the Polish mathematician Wacław Sierpiński, who described the pattern in 1915. It has appeared in Italian art since the 13th century. Though this adaptation of the design, the Sierpinski Square, looks complex, it can be generated with a short recursive function.

Your main task is to write a recursive function sierpinski() that plots a Sierpinski Square of order n to standard drawing.

Think recursively:

  • sierpinski() should draw either one dark or light square depending on the iteration number.
    • Draw a dark (black) square when n is even, or draw a light (white) square when n is odd.
  • then call itself to draw another square inside the current square, starting with a dark square.

Notes:

  • All dark squares must have its edges form 45 degree angles with the edges of the canvas.
  • All light squares must have its edges parallel to the edges of the canvas.
  • The canvas size is 1×1. The side length of the first black square is half diagonal length (diagonal = 1).
  • USE StdDraw to draw the squares. Refer to the Java file for specific information.
  • ALL squares are centered at (0.5, 0.5).
  • Autolab will call the main method in SierpinskiSquare.java to execute your code as well as test each function individually.

You need to compute half of the diagonal length to find the x and y coordinates to draw the dark filled polygon.

  • The center of the polygon is (0.5, 0.5).
  • Use the side length to compute half of the diagonal length.

The order of the vertices matters when drawing the dark square. See the image to the right to visualize.

The input arrays to StdDraw.filledPolygon must follow the counter clockwise order starting at the top x1, y1.

  • Index 0 has x1, y1.
  • Index 1 has x2, y2.
  • Index 2 has x3, y3.
  • Index 3 has x4, y4.

Problem by Jeremy Hui.

Before submission

  1. Collaboration policy. Read our collaboration policy here.
  2. Submitting the assignment. Submit SierpinskiSquare.java and Ladder.java via the web submission system called Autolab. To do this, click the Assignments link from the course website; click the Submit link for that assignment.

Getting help

If anything is unclear, don’t hesitate to drop by office hours or post a question on Piazza.

  • Find instructors office hours here
  • Find tutors office hours in Canvas -> Tutoring, RU CATS
  • Find head TAs office hours here
  • POST on Piazza in Canvas -> Piazza
  • In addition to office hours we have the CAVE (Collaborative Academic Versatile Environment), a community space staffed with lab assistants which are undergraduate students further along the CS major to answer questions.