Skip to Main Content

Introduction to Computer Science

Computer Science Department

Functions and Recursion – 50 course points

Recursive calls of functions using StdIn and StdOut Library to print graphics.

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.

Programming

Write 2 programs and submit on Autolab.

  • We provide a zip file (find it under Matryoshka on Autolab) containing Matyroshka.java and QuadraticKoch.java.
  • For each problem UPDATE and SUBMIT the corresponding file.

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 functions
  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.
  8. DO NOT print other messages, follow the examples for each problem.
  9.  
  10. ONLY print the result as specified by each problem. Observe the examples’ output and display only what the problem is asking for.
    1. DO NOT print other messages; follow the examples for each problem.

1. Matryoshka Doll (20 points)

The purpose of this assignment is to apply the concept of recursion by recursively generating a series of dolls to resemble the popular Russian nesting doll set, Matryoshka Dolls, which are a series of wooden dolls that are of decreasing size nested within one another.

Overview

Matryoshka Dolls are also known as nesting dolls that are of Russian origin. They consist of a set of dolls where each doll is progressively smaller than the one before such that they can be placed within one another.

As depicted here, in this assignment we will model the recurring design of the dolls as they decrease in size from left to right.

Task

  • We provide a zip file (find it in Autolab) that contains Matryoshka.java.
  • UPDATE and SUBMIT the corresponding file.

Programming

You will write 3 functions to draw the Matryoshka Doll: main(), drawDoll(), and stackDolls(). 

drawDoll() is an iterative function

Implement the drawDoll() function to create two circles representing the doll’s body and head.

  1. create a circle for the doll’s body centered at the parameters (x, y) values. The circle’s radius is the given by the radius parameter. 
  2. create another circle as the doll’s head that is placed on top of the body. The radius of the head is expected to be 1/2 the body’s radius.
  3. then call the drawFace() helper function which draws a smiley face on the doll’s head.
  • Use StdDraw to draw the design. Refer to the Java file for specific information.
  • Use the StdDraw.circle function to draw the doll’s body and head.
  • The StdDraw canvas size is 1×1 by default (and does not need to be changed). The bottom-left corner is the origin (0,0).

stackDolls() is a recursive function

Implement the recursive stackDolls() function that draws ONE doll and then recursively calls itself to draw more dolls. The function parameters are:

  • the (x,y) body coordinate and radius of the doll this function is drawing.
  • an integer that corresponds to the number of dolls to draw.
    • recall that each call to stackDolls() draws one doll, so this function call accounts for 1 doll.

Steps:

  1. this function uses the (x, y) coordinate and radius to draw a doll,
  2. then recursively calls itself to draw an adjacent doll body that is 5/7 times the size of the previous doll’s body. The function terminates when there are no dolls remaining to draw.
    • Note that the dolls are adjacent to each other, the side of their bodies touch, see the images below.

main() function

The main function is the entry point of the program. This is the function that that Java Virtual Machine (JVM) calls to start execution.

  1. main() will read one command-line argument representing the number of dolls to be drawn.
  2. then, it calls the stackDolls(0.1,0.1,0.1,numberOfDolls) function to draw a succession of Matryoshka dolls on the 1×1 StdDraw Canvas.

The following output is given when stackDolls() is called with the parameters x = 0.1, y = 0.1, r= 0.1, dolls = 5

  • VSCode Extensions

    You can install VSCode extension packs for Java. Take a look at this tutorial. We suggest:

    Importing VSCode Project

    1. Download Assignment6.zip from Autolab Attachments.
    2. Unzip the file by double clicking.
    3. Open VSCode
      • Import the folder to a workspace through File > Open Folder

    Executing and Debugging

    First navigate to Matryoshka directory/folder

    • to compile: javac Matryoshka.java
    • to execute: java Matryoshka n (where n is the number of dolls to draw)

    By Pooja Kedia

2. Quadratic Koch (30 points)

The purpose of this assignment is to practice recursion through writing a program that plots the Quadratic Koch Snowflake.

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.

  • See this video on how to import the files into VS Code and how to submit into Autolab.

Overview

The Quadratic Koch Curve is an example of a fractal pattern like the H-tree pattern from Section 2.3 of the textbook.

Your main task is to write a recursive function koch() that plots a Quadratic Koch Curve of order n to standard drawing.

Task

  • We provide a zip file (find it in Autolab) that contains QuadraticKoch.java.
  • UPDATE and SUBMIT the corresponding file.

Programming

Create the Quadratic Koch Curve according to the following design specifications:

  • USE StdDraw to draw the Koch Snowflake design. Refer to the Java file QuadraticKoch.java for specific information about the implementation. You only write in the QuadraticKoch.java file.
    • You will write two helper functions getCoords() and koch() as well as the main() function.
  • The StdDraw canvas size is 1×1 by default (and does not need to be changed).

main() function

The main function is the entry point of the program. This is the function that that Java Virtual Machine (JVM) calls to start execution.

  1. main() will read one command-line argument representing the order of the Quadratic Koch Curve to draw.
  2. then, it will call the koch()function 4 times. The coordinates of the four calls are shown below, starting with the bottom left vertex and moving in clockwise order.

getCoords() is an iterative function

This function computes and returns the set of coordinates to draw ONE segment of the Quadratic Koch Curve.

Use a 2D array where the first row stores the x-coordinates and the second row stores the y-coordinates. The position of the coordinates matters when drawing the Quadratic Koch Curve.

  • Note that x0, y0, x5, and y5 are provided as input parameters.
  • Use the image below to visualize how to compute the additional coordinates (x1, y1), (x2, y2), (x3, y3), and (x4, y4).
  • Hint: Think about how far x1 is away from x0 and how far x4 is away from x5. Use the same approach for the y values.

koch() is a recursive function

This function draws ONE segment of the Quadratic Koch Curve by recursively calling itself.

The image below shows the recursive calls in color.

  • koch()draws a line between the two points (x0, y0) and (x5, y5) using StdDraw.line()when order is zero (n == 0),
  • otherwise it recursively calls koch() on the right adjacent coordinates as shown below, with the order being one less.
  •  

Note that Autolab will call the main function in QuadraticKoch.java to execute your code as well as test each function individually.

    • VSCode Extensions

      You can install VSCode extension packs for Java. Take a look at this tutorial. We suggest:

      Importing VSCode Project

      1. Download Assignment6.zip from Autolab Attachments.
      2. Unzip the file by double clicking.
      3. Open VSCode
        • Import the folder to a workspace through File > Open Folder

      Executing and Debugging

      First navigate to QuadraticKoch directory/folder

      • to compile: javac QuadraticKoch.java
      • to execute: java QuadraticKoch n (where n is the order of the design)
       
    •  
    • The original Koch Snowflake was created by the Swedish mathematician Helge von Koch, who described the pattern in 1904.
    • If you’re interested in learning more about Quadratic Koch, visit https://en.wikipedia.org/wiki/Koch_snowflake.

    • By Jeremy Hui

Before submission

Collaboration policy. Read our collaboration policy here.

Submitting the assignment

Submit MatyroshkaDoll.java and QuadraticKoch.java separately 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 on Canvas -> Tutoring
      • Find head TAs office hours here
      • In addition to office hours we have the Coding and Social Lounge (CSL) , a community space staffed with lab assistants which are undergraduate students further along the CS major to answer questions.