Computer Science 210
Data Structures

Fall 2017, 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.

Getting Set Up

You will receive an email with the link to follow to set up your GitHub repository recursion-lab-yourgitname for this Lab. 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. At least one group member should make a clone of the repository to begin work.

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.

These programs will be graded as practice programs.

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 for this assignment. (2 points)

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. (6 points)

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. (9 points)

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. (2 points)

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. (6 points)

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. (9 points)

n Choose k

Now, we will consider the function Choose(n,k), which is the number of different ways you can choose k items from among n items. For example, if you have three items {a,b,c}, there are 3 ways to choose 2 of them: {a,b}, {b,c}, and {a,c}. So Choose(3,2) = 3.

This is a case where recursive thinking leads to an elegant solution. We can define Choose(n,k) recursively as follows: Choose(n,0) is 1 for all n >= 0, and Choose(0,k) is 0 for all k >= 1. For all n > 0 and k > 0, Choose(n,k) is equal to the number of ways you can choose k-1 items from among n-1 items added to the number of ways you can choose k items from among n-1 items.

First, write a main method in the Choose class that prompts for and reads in two positive integers that will be used as n and k. You need not worry about error checking the input for this assignment. (2 points)

Next, write a recursive method recNChooseK that uses that formulation to compute the value of Choose(n,k). Update your main method to call the recNChooseK method on the numbers entered by the user, and print out the value returned. (9 points)

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. These methods will be graded as practice programs.

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. (6 points)

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. (6 points)

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. (8 points)

Submitting

Your submission requires that all required deliverables are committed and pushed to the master for your repository's origin on GitHub. That's it! If you see everything you intend to submit when you visit your repository's page on GitHub, you're set.

Grading

This assignment is worth 100 points, which are distributed as follows: