CS 515 Assignment 2, Spring 2008

This assignment should give you practice with writing recursive functions. You are to implement, in a file called Recursion.java , all the methods described below.

You may use no looping structures (while, do-while or for) in any of you implementations.

Don't forget that if you have any trouble with a particular function it is critical to delete the problematic code and replace it with a skeleton that simply prints "NOT IMPLEMENTED", and returns a dummy value, If you include a questionable function that crashes the program, you risk losing all the points for the assignment.

The partition method that you need for kSmall is already written in Recursion.java. This function chooses its pivot, so you don't need to choose it.

• Style matters!
• Test fully and carefully.
• Make sure you start with a copy of Recursion.java on the class webpage.
• Make sure your implemented code works with test file: TestRecursion.java , also on the class webpage.

• pubpages.unh.edu/~cs515/a2/Recursion.java
• pubpages.unh.edu/~cs515/a2/TestRecursion.java

    // Returns a string, reversed.
    public String reverse(String s) { }

    // Converts a number to base 3.
    public String toBase3(int number) { }

    // Sums the first n elements of an array
    public int sum(int[] arr, int n) { }

    // Sums the first n elements of an array, but
    //      uses a tail-recursive helper method.
    public int sumTail(int[] arr, int n) { }

    // calculates an integer raised to a power
    public int pow(int base, int exponent) { }

    // Return index in array where item occurs LAST.
    public int lastIndexOf(int[] array, int n, int item) { }

    // Finds the smallest element in an array.
    public void min(int[] arr, int n) { }

    // Returns true iff the item appears in the array exactly k times.
    public boolean containsKTimes(int[] array, int n, int item, int k) { }

    // finds the kth smallest element in the array
    // (you may use swap and partition, already written)
    public int kSmall(int k, int[] arr, int first, int last) { }

    // returns true iff the argument is prime
    public boolean isPrime(int n) { }