Lab: Recursion
Download recursionlab.zip, which contains all the files you will need for this assignment.
Can you defeat the dreaded RecursionMonster.java?
Open Lab.java. You will be implementing a number of recursive methods in this file.
All solutions you write for this assignment must be recursive. You cannot use any for/while loops. You may, however, write any helper methods you like (as long as none of those helper methods use for/while loops). You cannot create any new arrays, ArrayLists, ListNodes, or other data structures except where otherwise stated.
Exercise 0: Just the Facts
Take a look at the fact method that has already been defined for you in Lab.java. This method recursively computes the factorial of a given integer n. Notice that fact is not static. To call it, you will first need to construct a Lab object and then call the fact method on it. For example:
new Lab().fact(4)
Test that you can call the fact method in this manner.
The Test.java file has been provided to help you follow your recursive calls and debug your work. There is one static method in this file for each of the methods in Lab.java. Go ahead and call the fact method in Test.java. For example:
Test.fact(4)
You should see a window pop up. Press the step button to step through the recursive calls. Keep pressing it until the button is disabled, indicating that the original method call has terminated with a result.
Going forward, you will probably choose to use the Test.java file to test each of the recursive methods you write in Lab.java.
The exercises below are roughly ordered from simplest to most challenging, but you may complete them in any order.
Exercises 1: product
Complete the product method, which takes in a linked list of integers and returns the product of those integers (the result of multiplying them together). For example, if the linked list contains [2, 3, 5], then product returns 2 × 3 × 5 = 30.
Exercise 2: withoutStars
Complete the withoutStars method, which takes in any string and returns a new string consisting of all the same characters in the same order, but without any asterisks. For example, withoutStars("*ab**c***") returns abc.
Exercise 3: sumSquares
Complete the sumSquares method, which takes in a non-negative integer n and returns the sum of the squares of all integers from 0 to n. For example, sumSquares(3) returns 0² + 1² + 2² + 3² = 14.
Exercise 4: replaceValueAt
Complete the replaceValueAt method, which takes in a linked list called list, an index, and a new value. The method replaces the value at the given index with the given new value. The method also returns the old value (the one that was replaced). For example, if list contains [A, B, C, D], then replaceValueAt(list, 2, "Z") returns C, and list now contains [A, B, Z, D]. Note that 0 <= index < size of list.
Exercise 5: pow
Complete the pow method, which takes in a base and a non-negative exponent, and returns the result of raising the base to the exponent using repeated multiplication. For example pow(3, 4) returns 3 × 3 × 3 × 3 = 81.
Note: Obviously you cannot use Math.pow in your solution.
Exercise 6: toLetterList
Complete the toLetterList method, which takes in any string and returns a linked list containing each of the characters from the string, in the same order. For example, toLetterList("ABCD") returns a linked list containing [A, B, C, D].
Exercise 7: sameList
Complete the sameList method, which takes in any two linked lists (with the same element types) and returns true if and only if both lists contain the same values in the same order. For example, sameList returns true for [A, B, C] and [A, B, C]. On the other hand, sameList returns false for [A, B, C] and [A, Z, C]. Likewise, sameList returns false for [A, B, C] and [A, B].
Exercise 8: reverse
Complete the reverse method, which takes in any string and returns a new string with the same characters in the opposite order. For example, reverse("ABCD") returns DCBA.
Exercise 9: fractal
This exercise requires you to use the DrawDisplay class, which has been provided for you. For example, the following creates a square window that is 100 pixels wide and 100 pixels tall.
DrawDisplay d = new DrawDisplay(100);
The top-left corner of the window has coordinates (0,0). The following draws a black square whose top-left corner is at (x = 10, y = 50). The square is 25 pixels wide and 25 pixels tall.
d.drawSquare(10, 50, 25);
Test that you can construct a DrawDisplay and draw a square on it.
Now complete the fractal method, which takes in a DrawDisplay and a square region. The square region is specified using the (x, y) of its top-left corner along with the size (side length) of the square. For example, the given square region might correspond to the dashed part of the DrawDisplay shown below.
The method also takes in a non-negative depth value. When the depth is 0, the method simply uses drawSquare to fill in the specified region. For example:
On the other hand, if the depth is greater than 0, fractal calls itself recursively on the upper-left, upper-right, and lower-left quadrants of the specified region, as shown below.
This requires three recursive calls, each with a depth one less than the given depth. For example, if fractal is passed a depth of 5, then it makes three recursive calls, each with a depth of 4.
But what will it look like when it works? Well, when fractal is called with depth 0, it simply fills in the square region.
When fractal is called with depth 1, it makes three recursive calls with depth 0, and each of those calls will fill in one square.
When fractal is called with depth 2, it makes three recursive calls with depth 1, and each of those calls will draw one L shape.
The Test.fractal method takes in only a single argument--the depth. Therefore, to draw a fractal of depth 0 (for example), call Test.fractal(0). Calling Test.fractal with a depth of 2 or less will pop up a window for stepping through the recursion. (Note: This window may appear behind the drawing window.) Calling Test.fractal with a depth of 3 or more will simply draw the final picture (without stepping).
Additional Credit Suggestions
Note that any methods must be written recursively in order to receive credit.
Your Own Fractals
Design and program your own fractal(s).
Hint: Instead of dividing the region into 2x2, divide it into a 3x3 grid, recursively calling your method in a subset of those sub-regions. Consider calling drawSquare in some places and using recursive calls in others.
Method: isPrime
Complete the isPrime method, which takes in a positive integer and returns true if and only if that number is prime. For example, isPrime(5) returns true and isPrime(6) returns false.
public static boolean isPrime(int n)
Hint: Try writing isPrime with a for/while loop first. Notice that one of your variables keeps changing as you loop. Now write isPrime recursively, with two parameters: n and that variable you identified. Finally, write the real isPrime method, which only takes in n and simply calls the recursive method you wrote with the extra parameter.
Method: max
Complete the max method, which takes in a non-empty array of integers and returns the largest integer in the array. You cannot construct any new arrays or other data structures in your code.
public static int max(int[] a)
Hint: Try writing max with a for/while loop first. Notice that one of your variables keeps changing as you loop. Now write max recursively, with two parameters: an array and that variable you identified. Finally, write the real max method, which only takes in an array and simply calls the recursive method you wrote with the extra parameter.
Method: sublist
Complete the sublist method, which returns a new list containing the subset of values in the given linked list that add up to the given sum. For example, if list contains [1, 3, 5, 7, 12], then sublist(list, 18) returns a new list containing [1, 5, 12], and sublist(list, 30) returns null. You may choose to have your method return a linked list or ArrayList.
public static ListNode<Integer> sublist(ListNode<Integer> list, int sum)
public static ArrayList<Integer> sublist(ListNode<Integer> list, int sum)
Hint: Good luck!