Computer Science 210
Data Structures

Fall 2018, Siena College

Home     Syllabus     Schedule     Examples     Style Guide

This week's lab will give you lots more practice with recursive methods. You will be assigned a partner for this lab. Only one submission per group is needed.

As you finish each step, please have your instructor initial the hard copy of this lab handout you were issued to indicate successful completion.

Names:

Learning goals:

1. To learn how to trace recursive methods manually to determine their output.
2. To practice setting up a recursive mathematical function, both in mathematical notation and in Java.
3. To practice writing test cases.
4. To write a Javadoc comment for a method.

Submitting

As you complete each programming task, commit with a meaningful commit message and push to your group's GitHub repository for this lab.

Once all written items are initialed to indicate completion, turn in the hard copy of this lab handout you were issued.

Getting Set Up

You will receive an email with the link to follow to set up your GitHub repository for this Lab (recursion-lab-yourgitname). One member of the group should follow the link to set up the repository on GitHub, then that person should email the instructor with the other group members' GitHub usernames so they can be granted access. This will allow all members of the group to clone the repository and commit and push changes to the origin on GitHub.

Please answer lab questions in the README.md file in your group's GitHub repository.

Remember, no work will be graded unless the names of all group members are in each file.

Tracing Recursive Methods

public void f(int n) {
    System.out.println(n);
    if (n > 1) {
        f(n - 1);
    }
}

public void g(int n) {
     if (n > 1) {
        g(n - 1);
     }
     System.out.println(n);
}


public void h(int n) {
    System.out.println(n);
    if (n > 1) {
        h(n - 1);
    }
    System.out.println(n);
}

Iteration vs. Recursion

For this part of the lab, you will be writing a series of Java applications similar in structure to the Powers example. As in that example, you will need to create a keyboard Scanner to read in a number from the terminal and use System.out.println to issue a prompt and report your answer.

Factorials

The first problem we are going to solve is that of computing factorials. From math, you know that the factorial of a positive integer n, denoted n!, is the product of all the numbers from 1 up to n.

First, write a main method in the Factorial class that prompts for and reads in a positive integer. You need not worry about error checking the input.

Next, write an iterative method loopFactorial that takes a single int as its parameter and returns the factorial of that value. Recall that an iterative method uses loop structures like for and while loops to do its work. Also update your main method to call the loopFactorial method on the number entered by the user, and print out the value returned.

Finally, write a recursive method recFactorial that uses that formulation to compute factorials. Also update your main method to call the recFactorial method on the number entered by the user, and print out the value returned. You should leave in the call to loopFactorial so you can see that the answers are consistent.

Sum of Squares

The next problem we are going to solve is that of computing the sum of the first n squares.

First, write a main method in the SumSquares class that prompts for and reads in a positive integer. You need not worry about error checking the input for this assignment.

Next, write an iterative method loopSumSquares that takes a single int as its parameter and returns the sum of the squares up to that value. Also update your main method to call the loopSumSquares method on the number entered by the user, and print out the value returned.

Finally, write a recursive method recSumSquares that uses that formulation to compute the sum of squares. Also update your main method to call the recSumSquares method on the number entered by the user, and print out the value returned. You should leave in the call to loopSumSquares so you can see that the answers are consistent.

Recursive Printing and Drawing

In the class RecursivePractice, you will find three methods to be completed. Rather that writing a main method that calls these, we will test them by running them directly in BlueJ. You will be shown/reminded how to do this during lab.

Complete the recursive method printIt so that it prints n asterisks, followed by the same number of exclamation points. For example, printIt(5) would print "*****!!!!!". Use recursion. Use no loops or local variables. The base case is provided.

Next, consider the rectangle of asterisks below. It has width 10 and height 5. You could define this rectangle recursively as a rectangle of width 10 and height 4 followed by a row of 10 asterisks. A height 0 rectangle is the base case, in which case nothing is printed.

Complete the drawRectangle method, which recursively draws a rectangle of width w and height h. Note that you may not use a loop over the h rows, but you may use a loop to print the w asterisks in a given row.

Finally, consider the right triangle of asterisks below. It has a base of length 6. Think about how you could define this triangle recursively.

     *
    **
   ***
  ****
 *****
******

Complete the method drawRightTriangle which recursively draws a triangle of base length b. The second argument is the number of spaces that appear before the base of the triangle. For example, for the base 6 triangle above there are 0 spaces before the base, so you would invoke the method with b = 6 and leadingSpaces = 0. But if you remove the bottom row from this triangle, you are left with a triangle of base length 5 with 1 leading space before the base.

Don't forget to commit and push all of your code for this lab to your group's GitHub repository.