CS 163/164, Spring 2017

Programming Assignment - P11

Recursion

Due Monday, Nov. 13th at 6:00 pm

Late Tuesday, Nov. 14that 8:00 am

Objectives of this Assignment

Implement a set of recursive methods
Learn how to use helper methods to solve recursive problems

Description

In this assignment you will write a number of recursive methods. Create a P11 project and class - you will implement the following interface: IP11.java
There is no input file.

P11

P11 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. Any programs with loops found in them will be given a zero. Here are the methods in P11 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)

Note: Your helper method signature may not match this, it is offered only as an example.

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?

Grading

100 points for perfect submission.
0 points for no submission, will not compile, submitted class file, etc.
Preliminary Tests
- compileTest: checks that program compiles. (0 points)
- test1: printPattern (20 points)
- test2: convertNumt (20 points)
- test3: intersection (20 points)
Final Tests
- test4: printPattern (10 points)
- test5: convertNumt (15 points)
- test6: intersection (15 points)
- Final grading includes the preliminary tests.

Submitting Your Assignment

Submit P11.java to the Checkin tab.