CSCI 51, Spring 2009

Program 7: Recursion and OOP (Object-Oriented Programming)

100 points

Assigned: Tuesday, April 7
Due: Monday, April 13 at 11:55 pm

This assignment has you turn in three java files, Rec.java, Ipod.java, and UseIpod.java.

Program 1: Working with Recursion (50pts)
Create a class named Rec in a file named Rec.java and introduce the following methods. These methods will
naturally be static methods.

(5 pts) Write a recursive method called power that takes a double x and an integer n and that returns x^n.
Hint: a recursive definition of this operation is power(x, n) = x * power(x, n - 1). Also,
remember that anything raised to the zeroth power is 1. In your main call power as follows:

System.out.println("power(3, 0) = " + power(3, 0));
System.out.println("power(2, 5) = " + power(2, 5));
System.out.println("power(3, 4) = " + power(3, 4));
(5 pts) This following algorithm is known as Euclid’s Algorithm because it appears in Euclid’s Elements
(Book 7, ca. 300 B.C.). It may be the oldest nontrivial algorithm. The algorithm is based on the observation
that if r is the remainder when a is divided by b, then the common divisors of a and b are the same as the
common divisors of b and r. Thus we can use the equation:
gcd(a, b) = gcd(b, r)
to successively reduce the problem of computing a GCD to the problem of computing the GCD of smaller
and smaller pairs of integers. For example,
gcd(36, 20) = gcd(20, 16) = gcd(16, 4) = gcd(4, 0) = 4
implies that the GCD of 36 and 20 is 4. It can be shown that for any two starting numbers, this repeated
reduction eventually produces a pair where the second number is 0. Then, the GCD is the other number in
the pair.

Write a recursive method called gcd that takes two integer parameters and that uses Euclid’s Algorithm to
compute and return the greatest common divisor of the two numbers. In your main call gcd as follows:

System.out.println("gcd(36, 20) = " + gcd(36, 20));
System.out.println("gcd(34, 0) = " + gcd(34, 0));
System.out.println("gcd(3346, 468) = " + gcd(3346, 468));
(5 pts) The Ackermann function is defined for non-negative integers as follows:

A(m, n) = :
                        n + 1 if m = 0
                       A(m − 1, 1) if m > 0, n = 0
                       A(m − 1,A(m, n − 1)) if m > 0, n > 0

Write a recursive method called ack that takes two ints as parameters and that computes and returns the
value of the Ackermann function. Try large numbers and explain to yourself what is happening. In your
main call ack as follows:

System.out.println("ack(1, 10) = " + ack(1, 10));
System.out.println("ack(2, 4) = " + ack(2, 4));
System.out.println("ack(3, 3) = " + ack(3, 3));
(10 pts)We have seen how to use the charAt, substring, and length functions defined on String.
In fact, for substring, we saw two variations: one taking one argument and another taking two arguments.
You will be using those functions (and others if you need) to solve the next several problems. First,
write a recursive method called printBackward that takes a String as a parameter and that prints the
letters of the String backwards (one character per line). It should be a void method. In your main call
printBackward as follows:
printBackward("Java Fun!");
(10 pts) Write a recursive method called printString that does the same thing as printBackward
but that prints the String in the same order of characters in the String given as the argument (one
character per line). In your main call printString as follows:
printString("Java Fun!");
(15 pts) Write a recursive method called reverseString that takes a String as a parameter and that
returns a new String as a return value. The new String should contain the same letters as the parameter,
but in reverse order. For example, the output of the following code
String reversed = reverseString("Java Fun!");
System.out.println(reversed);

Submit Rec.java.

Program 2: Ipod's (50 pts)
Create a class named Ipod in a class named Ipod.java. It is typically spelled iPod, but let’s follow our naming
convention and use Ipod instead. As usual you should also create another class named UseIpod in a file named
UseIpod.java.

Your end result should satisfy the following:
Write a piece of code in the main of UseIpod to test each aspect of the requirements I describe below as
you go. Remember to do incremental development: build a little bit of Ipod and test that much in UseIpod
before you add more. Repeat this process until you are done. In the end I want to be able to see your main
and feel that your Ipod class implementation was adequately tested.

An iPod should contain at least the following attributes: name, price, display size (diagonal length in inches),
memory capacity (in mega bytes), and whether it has a built-in wi-fi or not. I want you to add at least two
additional attributes that I did not mention. I want you to be careful in selecting the type of each field as you
design your class: int, double, boolean, String, etc. I want your decisions to be reasonable!
Add appropriate constructor(s), getters, and setters. Don’t blindly add a getter and setter for each field.
Think about each attribute and decide whether to provide a getter and/or setter or none.
Each iPod that is produced, i.e., each iPod object that gets created, must also have a serial number. To
assign a unique serial number to each Ipod object, you need to come up with a way to generate a unique
serial number. Include that capability in your Ipod class, and use it appropriately.
Your Ipod class should also be capable of remembering all the iPod objects that have been created so far,
and manage them. Hints: use an array of Ipod objects as a static field. Assume that the number of iPod
objects that will ever be created will never exceed 100.
Now add a method to iPod class that we can call to remove an Ipod object from that array. When you
remove one iPod object from some location in the array, you don’t want to leave a ’hole’ in the middle of
the array somewhere. I suggest you fill the hole somehow. One possibility would be to shift everything
beyond the hole to the left one position. A little easier solution would be to move the last one into the hole.
A couple of things to think about here: (1) when you move the last one into the hole, you need to set the
location where the last one was in to null. (2) In addition to the size of the array you also need to know
how many of the 100 positions in the array have been filled so far. This could be another static field that
gets updated every time an Ipod object is added to or removed from the array. If you have 23 positions
filled in so far, I assume those 23 iPod objects are occupying the locations 0 through 22, and the locations
from 23 to 99 are filled with null’s.
Also add a method that you can call to add an Ipod object to the array.
Add another attribute to Ipod class for the number of songs that have been loaded to each iPod object.
Add a method to Ipod class that we can call to find out about the total number of songs that have been
loaded to all the iPods in the entire system.

Hints: You will need to be careful as to what needs to be static and what needs to be non-static. What needs
to be private and what needs to be public. In my specification I intentionally left things open on these issues
so that you can think about them and make reasonable decisions.

Hand in Ipod.java, UseIpod.java