Prerequisite: See Intro to Recusion.
Review: To write a recursive method for some task, ask yourself three questions:
One key point we made was to trust that your friend does their job. Don't think about how your friend does their job (this often gets messy). Just make sure you do your job.
Preparation:
In the Interaction Pane, you can type:
import static RecListEx.* RecList r = list1(); RecList s = list2();The first line above imports all the static members in RecListEx.java. As a result list1() is the same as RecListEx.list1(), it just saves some typing.
The RecList class definition begins as follows:
/** A singly linked list. This provides a simple framework for
* exercises in reading and writing recursive methods, i.e.
* recursive puzzles. Have fun.
* There is a more advanced version of RecListAdv.java with additional
* recursive methods you are asked to write.
* Author: ADJ, based on an earlier example by RR */
public class RecList {
/** The element stored in the head element. */
public Object value;
/** Reference to the rest of the list. */
public RecList link;
/********************* Constructors ***********************/
/** Initialize this to store o.
* @param o the value for this list node. */
public RecList(Object o) {
value = o;
// link == null by default
}
/** Initialize this to store o in the first element
* and to link to r for the rest of the list.
* @param o the value for this list node.
* @param r the rest of the list. */
public RecList(Object o, RecList r) {
value = o;
link = r;
}
/**************** Non-recursive Methods ********************/
/** Returns the data value for the first node of this list.
* @return the value in the first node. */
public Object first() {
return value;
}
/** Inserts a node with the value o to the head of this list.
* @param o the data item to use for the new head.
* @return a reference to the new list. */
public RecList prepend(Object o) {
return new RecList(o, this);
}
/** Returns the rest of this list (2nd through to the end nodes).
* @return the rest of the list (null if the list is currently
* length 1). */
public RecList rest() {
return link;
}
/**************** Recursive Playing Around ********************/
/** Returns a String representation of all the data in me.
* @return my contents as a String. */
public String toString() {
if (value == null) {
if (rest() == null) // No more items in list.
return "null";
return "null" + " " + rest().toString();
}
// first value is not null
if (rest() == null)
return value.toString();
return value.toString() + " " + rest().toString();
}
/** Determines if any data item in this list satisfies o.equals(item).
* Precondition: o cannot be null.
* @param o the object to search for.
* @return true if o is in the list. */
public boolean contains(Object o) {
throw new UnsupportedOperationException("Not implemented yet.");
}
/** Returns true if any data value in me is null.
* @return whether any node in the list has a value equal to null. */
public boolean containsNull() {
throw new UnsupportedOperationException("Not implemented yet.");
}
/** Returns a copy of me. A shallow copy is performed. That
* is, the data objects referenced by the list are not
* copied themselves, only their references are copied.
* @return the copied list. */
public RecList copy() {
throw new UnsupportedOperationException("Not implemented yet.");
}
/** Appends a copy of list2 to the end of me.
* @return the updated list. */
public RecList append(RecList list2) {
throw new UnsupportedOperationException("Not implemented yet.");
}
/** Returns a new list which is a copy of me
* but in the reverse order.
* @return the reversed copy. */
public RecList reverse() {
throw new UnsupportedOperationException("Not implemented yet.");
}
// And so on... several more methods to be written.
} // end RecList
In class we wrote the following methods (we have also included the answer to Q#1 above):
For example:
/** Returns a copy of me. A shallow copy is performed. That
* is, the data objects referenced by the list are not
* copied themselves, only their references are copied.
* @return the copied list. */
public RecList copy() {
if (rest() == null)
return new RecList(value);
return rest().copy().prepend(value);
}
/** Appends a copy of list2 to the end of me.
* @return the updated list. */
public RecList append(RecList list2) {
if (list2 == null)
return this;
if (rest() == null) // No more items in list.
link = list2.copy();
else
link = rest().append(list2);
return this;
}
/** Returns a new list which is a copy of me
* but in the reverse order.
* @return the reversed copy. */
public RecList reverse() {
if (rest() == null) // No more items in list.
return new RecList(value);
return rest().reverse().append(new RecList(value));
}