CS 161 Assignment 4
Recursion

Due 9/25 @ 8:00pm

Late 9/27 @ 8:00am

Overview

In this assignment you will write a number of recursive methods. You are given a starting Assign4 code:

Assign4.java

There is no input file.

Assign4

Assign4 is the only class in this assignment. You can exercise your methods more by extending the main method. We will test your code using a testClient class. Do not change the signature of the specified methods. You can however, and are advised to, create your own helper methods.

You will use ***RECURSION ONLY*** in this assignment, i.e., there will be no loops in any of the methods you implement. Here are the methods in Assign4 that you will implement.

void printPattern(int n)

Precondition: n>0
Postcondition: print a pattern of n+1 lines ( 0 to n ):
line i (i = 0 to n) has i stars ("*"), followed by (n-i) stripes ("-")

For example, printPattern(3) prints:

---
*--
**-
***

hint: use a private recursive helper function, with more parameters, that does the work, e.g.:

  private void printPattern(int stars, int stripes)

You may need another helper function...

int convertNum(int[] num)

Precondition: num.length > 0, and num contains digits between 0 and 9 (inclusive)
Postcondition: return int representation of num

For example

  int[] num123 = {1,2,3};  
convertNum(num123) returns 123

hint: use a private recursive helper function, with more parameters, that does the work, e.g.:

  private int convertNum(int[] num, int atIndex, int lastIndex, int result)

ArrayList intersection( ArrayList AL1, ArrayList AL2)

Precondition: AL1 and AL2 are not empty, and elements in AL1 are unique, and elements in AL2 are unique, (but AL1 and AL2 can contain the same elements)
Postcondition: return an ArrayList with elements that are in both AL1 and AL2, *** in the order they occur in AL1 ***, and *** leave AL1 and AL2 unchanged ***

For example:

  ArrayList AL1 = new ArrayList();
  ArrayList AL2 = new ArrayList();
  AL1.add("a"); AL1.add("b"); AL1.add("c");
  AL2.add("b"); AL2.add("c"); AL2.add("d"); AL2.add("e");
  ArrayList intersect = A3.intersection(AL1,AL2);
  System.out.println(AL1 + " intersect " + AL2 + " = " + intersect);	
prints:
[a, b, c] intersect [b, c, d, e] = [b, c]

hint: What kind of helper method would you use here?

Submitting Your Assignment

Use the CS161 Checkin website to test and submit your program Assign4.java.

CS 161 Assignment 4 Recursion