Fall 2018, Siena College

Lab 4: Recursion
Due: 3:30 PM, Tuesday, October 16, 2018

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.

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

Tracing Recursive Methods

Question 1: For each of the methods below, trace the execution by hand to determine the output when each is called with inputs 1, 2, 3, and 4. (16 points)

```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.

Question 2: What are the values for n! for values of n=1, 2, 3, 4, and 5? (2 points)

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.

Question 3: Demonstrate your loopFactorial method and its use in your main method. (6 points)

Question 4: Write a recursive mathematical formulation, along the lines of the second power formula in the notes, for computing n!. (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.

Question 5: Demonstrate your recFactorial method and its use in your main method. (12 points)

Question 6: Draw a recursive call diagram showing all of the method calls needed when recFactorial(6) is called. Be sure to include the value of the formal parameter for each, and show its return value. (12 points)

Sum of Squares

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

Question 7: What are the values for the sum of the first n squares for values of n=1, 2, 3, 4, and 5? (2 points)

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.

Question 8: Demonstrate your loopSumSquares method and its use in your main method. (4 points)

Question 9: Write a recursive mathematical formulation, along the lines of the second power formula in the notes, for computing the sum of the first n squares. (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.

Question 10: Demonstrate your recSumSquares method and its use in your main method. (12 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.

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.

Question 11: Demonstrate your recursive printIt method. (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. 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.

Question 12: Demonstrate your recursive drawRectangle method. (8 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.

Question 13: Demonstrate your recursive drawRightTriangle method. (8 points)

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