Home Previous Next

CSC205AA::Lecture Note::Week 07
GDT::Bits:: Time  |  Weather  |  Populations  |  Special Dates

Overview
Code[recursion] PrintLD.java | Fibonacci.java | GCD.java {GCDverbose.java}
[multi-dimensional arrays] MultiArrays.java | TwoDimensionalArrays.java | BYTES.java | ThreeDimensionalArray.java
[interfaces] InterfaceExample.java | InterfaceEG.java | I_ExitStatus.java | TestI_ExitStatus.java
[interfaces continued] TestSerializable.java | TestClone.java | CSC205_Containers
[memory/heap/stack] Memory.java

Recursion

Recursion is any solution technique in which large problems are solved by reducing them to smaller problems of the same form.

According to multiple sources, the text `Thinking Recursively` by Eric Roberts (John Wiley 1986) is an excellent resource on recursion.

Internally, recursive functions are supported using a stack.

Almost every recursive function has the same basic structure:

```   if (test for simple case)
return (simple solution computed w/o using recursion)
else
return (recursive solution involving a call to the same function)
```

A recursive function is a function that calls itself in its function body. The call uses different arguments that ultimately read values that allow the function to return a result.

A recursive algorithm must have a well-defined stopping state, or termination condition.

Tail recursion is when the only recursive call appears in the function and that recursive call is the last operation performed at that procedural level. Typically, tail recursive functions can be easily rewritten as non-recursive functions. The traverse linked-list example provides an example of tail recursion.

• Recursion replaces the loop.
• Recursion may provide no saving in storage, since somewhere a stack of the values being processed must be maintained.
• Recursion will not be faster.
• Recursive code is more compact, and often much easier to write and understand than the non-recursive equivalent.
• Recursion is especially convienent for recursively defined data structures likes trees.
• Recursive procedures can be carried out with a stack.

Interesting Recursion Related Tidbit

Headline: "Microsoft's Java JIT compiler bungles tail recursion."

A programmer from England has discovered a flaw in Microsoft's Java environment running in Internet Explorer under Windows. On 10/20/1998 Andrew Kennedy posted a note to Java programming newsgroups showing that jview, Microsoft's command-line interface to its just-in-time compiler, calculates the factorial of 5 (i.e., 5 * 4 * 3 * 2 * 1 * 0!) to be 16. Kennedy writes:
> Microsoft seem to have confused addition with multiplication. > Such an easy mistake to make.
Followup postings pin down the likely source of the bug as incorrectly handled tail recursion in Microsoft's JIT compiler. Unfortunately there seems to be no way to turn off JIT. Kennedy speculates that this error may be responsible for the failure of a large number of Java applets to run in the IE 4 environment.

The Factorial Example

Computing the factorial of a number is popular example of using recursion.

```   Mathematically:  n! = { 1  if n = 0; otherwise,  n * (n-1)! }
```

To compute `n!` you must:

1. remember what  `n`  is
2. go compute  `(n-1)!`
3. once  `(n-1)!`  is computed, multiply by  `n`  to get the final answer
```   To compute (n-1)!, you 1st compute (n-2)!.  Computing (n-2)!
requires finding (n-3)! and so on.  Eventually we end up at 0!
and 0! is defined to be the value 1.

In C:
printf("%i\n", factorial(4));

int factorial(int n) {
if (n == 0) return 1;
return n * factorial(n -1);
}

4 is pushed onto the stack
3 is pushed onto the stack
2 is pushed onto the stack
1 is pushed onto the stack
0 is pushed onto the stack
returns 1
1 * 1 returns 1
2 * 1 returns 2
3 * 2 returns 6
4 * 6 returns 24
```
See factorial.cpp and Factorial.java.

Recall: When a function is called, EXPRs are evaluated and are passed by value. An implicit argument that is passed to a function is a return address. Function return values, if any, are placed in a secure location from which the calling program may retrieve it.

The Power Example

Raising a number to a power can also be solved recursively.
```   Power function:   n**k = { 1  if k is 0; otherwise, n * (n**(k-1)) }
```
Computing  `xn` , where  `x`  is a real number and  `n`  is a non-negative integer, is called the power function and its calculation is usually accomplished with repeated multiplication:
```   xn = x * x * x * ... *x * x

where  x  multiplied with itself  n  times

20 = 1
21 = 2 * 1 = 2
22 = 2 * 2 = 4
23 = 2 * 2 * 2 = 8
24 = 2 * 2 * 2 * 2 = 16
```
The power function can be implemented as follows:
```
power(x, n) = xn = { 1, n = 0 | x * xn-1, n > 0 }

double power(double x, int n) {
if (n == 0) return 1;
return x * power(x, n-1);
}

```
See power.cpp and Power.java.

Coverting an Integer to a String

```   printd(150);

printd(int n) {
if (n / 10)
printd(n / 10);
putchar(n % 10 + '0');
}

150 / 10 -- 15 pushed onto the stack
15 / 10 -- 1 pushed onto the stack
1 / 10
1 is printed
5 is printed
0 is printed
```
See printld.cpp and PrintLD.java.

{TopOfPage} {Oracle.com::API Specification | Tutorial} {Additional Resources}

Multi-dimensional Arrays

Multi-dimensional arrays are arrays-of-arrays. Example: a two-dimensional array is an array of one-dimensional arrays.

```   int someArray[][];  // someArray  will reference an array whose elements
// are of type:   array-of-int

someArray = new int[];
for (int i = 0; i < someArray.length; i++)
someArray[i] = new int;

int  int   int   int   int
int  int   int   int   int
int  int   int   int   int

/*
* example of a jagged two-dimensional array
*/
a = new int[];
for (int i = 0; i < a.length; i++)
a[i] = new int[i + 1];

int
int  int
int  int  int
int  int  int  int

The EXPR  a[i]  accesses the  i'th   one-dimensional array.

The following code snippet creates a 2x3 table of Foo objects.

Foo[][] foo = new Foo;
for (int i = 0; i < foo.length; i++)
for (int j = 0; j < foo[i].length; j++)
foo[i][j] = new Foo();

or

Foo[][] foo = new Foo[];
for (int i = 0; i < foo.length; i++)  {
foo[i] = new Foo;
for (int j = 0; j < foo[i].length; j++)
foo[i][j] = new Foo();
}
```

Excluding some mathematical and scientific computing, multi-dimensional arrays rarely exceed two dimensions.

MultiArrays.java

{TopOfPage} {Oracle.com::API Specification | Tutorial} {Additional Resources}

Interfaces

From the The Java Programming Language by Arnold, Gosling, Holmes.

The fundamental unit of programming in Java is the class, but the fundamental unit of object-oriented design is the type. Interfaces define types in an abstract form as a collection of methods or other types that form the contract for that type.

An interface is defined using the keyword `interface` rather than `class`.

An interface contains no instance variables, nor does it contain any method implementations. You cannot create instances of an interface.

```   interface Foo { ... }

//! Foo f = new Foo();   // not legal
```

An `interface` can declare three kinds of members:

• constants
• methods
• nested classes and interfaces

All interface members are implicitly `public`.

A `class` guarantees to implement the methods of an interface by using the `implements` keyword when the class is defined.

```   class X implements Y
```

Any class that implements an `interface` must define (i.e. implement) the methods, if any, declared in the `interface`.

A class can implement more that one interface. In addition, a class can extend another class and still implement one or more interfaces.

```   class X implements Y, Z { ... }
class X extends A implements Y, Z { ... }
```

To an extent, interfaces support the concept of multiple inheritance.

Common interfaces from the `java.lang` package:

• `Enumeration`  -- class must implement the `hasMoreElements()` and `nextElement()` methods
• `Cloneable`  -- class must implement the  `clone()` method
• `Runnable`  -- used with threads; class must implement the   the  `run`  method

An interface can be used to "tie" together classes that are in separate inheritance trees.

```                  Object
|
Assignment               Interface:  Submitable
|
Exam   Program   Homework
...    ...       ...

Object
|
Game                       Interface:  Submitable
|
Guessing  Yahtzee   Blackjack
...       ...       ....
```

An interface can be used to encapsulate a collected of related manifest constants (i.e. simulate an `enum` in C).

```   interface ExitStatus {
int EXIT_SUCCESS = 0;
int EXIT_FAILURE = 1;
}
```

When an `interface` declares named constants, then they are implicitly defined to be `public`, `static`, and `final`. [blank finals are not allowed]

Methods declared in an interface are implicitly `abstract`.

An interface can extend (i.e. inherit) other interfaces.

```   interface Sortable { ... }
interface Searchable { ... }
interface Container extends Sortable, Searchable { ... }
```
Any class that implements `interface Container` must also implement the `Sortable` and `Searchable` interfaces.

Although you cannot instantiate an object using an interface, you can use an interface as the type for variable and assign to that variable any object whose class implements the interface. This allows for polymorphic run-time binding.

```   interface Container { ... }

class List implements Container { ... }

List list = new List();
...
Container c = list;  // list is a container
```

From a naming convention perspective, many interfaces have a -able suffix applied to them.

{TopOfPage} {Oracle.com::API Specification | Tutorial} {Additional Resources}

Object Serialization

Any object that implements the `Serializable` interface can be turned into a sequence of bytes that can be restored fully into the original object.

Benefits.

• don't have to worry about data representation
• don't have to worry about byte ordering

The `Serializable` interface is used as a flag -- it has no methods. Some objects may not want to be serialized.

To serialize an object you create some sort of ``` OutputStream``` object and wrap it inside an `ObjectOutputStream` object. Then, the object can be serialized by calling `writeObject()`. Reversing the process is accomplished by creating an `InputStream` inside a `ObjectInputStream` and calling the `readObject()` method.

When an object is serialized, so are all the references it may contain to other objects.

```- Object Serialization (java1.1)
* useful for saving the state of an application/applet
* objects serialized/deserialized with  ObjectOutputStream  and
ObjectInputStream, respectively, using the  writeObject()  and
* primitive types written to stream as if using DataOutputStream;
otherwise,  writeObject() is called recursively to serialize
other objects (arrays, strings, objects) -- infinite recursion
is not a problem (so they say); can end up with an entire
graph object serialized
* not all objects can or should be serialized
* a class is serialable iff it implements Serializable
(or Externalizable); no methods defined -- it is a
marker interface
* Component implements Serializable; thus, all AWT components
can be serialized
* transient  indicates that a field should not be serialized
* custom serialization is accomplished by overriding  writeObject()
and  readObject(), and by using  defaultWriteObject()  and
defaultReadObject() -- note: they must be declared  private
* classes are assigned a version # -- cannot deserialize a
class that has a different version # than what was used when
it was serialized;  'serialver'  program
+ static final long serialVersionUID = 19971209L;
* serialized applets
+ <applet code=appletName.ser ...>
+ applets can be shipped in a pre-initialized state
* Externalizable
+ ObjectOutputStream and ObjectInputStream use the
of writeObject() and readObject(); allows the class
to take complete control over writing/reading their state
```

{TopOfPage} {Oracle.com::API Specification | Tutorial} {Additional Resources}

Object Cloning

Objects cannot be cloned unless they are created using a class that implements the `Cloneable` interface.

For a class to use the default implementation of `Object.clone()`, it must implement the `Cloneable` interface.

The `Cloneable` interface is an empty interface -- it is used as a tag only. In many cases, classes that can be cloned override `Object.clone()`.

`Object.clone()` does a bit-wise copy, which works fine for primitive types, but not necessarily with references. Only individual classes know how to be cloned (if at all). By default, a shallow copy is done versus a deep copy.

If an attempt is made to clone an object that is not cloneable, then the `CloneNotSupportedException` exception is thrown. This is a checked exception; therefore, it must be caught.

It is common for cloneable classes to override `clone()` so as to make it `public` rather than `protected`.

```   The Population class extends class X (which is cloneable), and it
contains numerous primitive types and a bunch of object references:

try {
Population p = (Population)super.clone();
p.name = new String(getName());
p.growthRate = (GrowthRate)growthRate.clone();
p.density = (Density)density.clone();
return p;
} catch (CloneNotSupportedException e) { return null; }
```

From the CoreJava book.

Why clone? You never want to return a mutable object as the value of a method because this violates encapsulation. As a rule of thumb, always use `clone` whenever you need to return a copy of a mutable data field.

When you start dealing with objects instantiated from classes that you do not know well, then how they clone becomes an unknown.

Here is an example of a program that will result in the throwing of a `CloneNotSupportedException`.

```   class A {
int a;
public A (int i) { a = i; }
public Object clone() throws CloneNotSupportedException {
return super.clone();
}
}
public class Main {
public static void main(String[] arg) {
A a1 = new A(260);
try {
A a2 = (A)(a1.clone());
} catch (CloneNotSupportedException e) {}
}
}

The execeptions occurs because class A calls Object.clone(),
but it does not implement the  cloneable  interface.
```

{TopOfPage} {Oracle.com::API Specification | Tutorial} {Additional Resources}

Lists

A  list  is a linear data structure whose components can only be accessed sequentially, one after another.

The first item is a list is called the  head  or  front  and the last item is called the  tail ,  back  or  end.

Lists have the following features:

• varying lengths (a list grows when items are added to it, and it shrinks when items are removed)
• homogeneous components (e.g. list of integers, list of prime numbers, list of `string` objects)
List operations include:
• define a list
• check if a list is empty
• check if a list is full
• reset (move list cursor to front of the list)
• end-of-list (move list cursor to back of the list)
• get current item
• insert before current item
• insert after current item
• remove item

GDT::Java::Code::GoofyIntList.java

{TopOfPage} {Oracle.com::API Specification | Tutorial} {Additional Resources}

Sets

A set is a basic building block of mathematics and is a collection of objects (e.g. integers, real numbers, boolean values, geometric points, strings, records, etc.).

The objects of a set are called elements (or members).

A set the following properties:

• all elements of a set belong to some universe
• any object of the universe is either in a set or it is not
• there is no particular ordering of elements within a set

Example of sets:

• a set of classes that a student it taking
• a set of prime numbers

The following operations are performed on a set:

• construct (i.e. define/create/instantiate) a set
• check to see if an object is a member of a set
• test if a set is empty
• get the cardinality (size of a set; number of elements/members)
• check if set A is included in set B (if so, then A is subset of B and B is superset of A)
• determine union of two sets (all elements appearing in A or B)
• determine intersection of two sets (all elements appearing in A and B)
• difference between to sets (all elements of set A not in set B -- notation: A - B)
• add an object to a set
• remove an object from a set
• clear all objects from a set

An array (i.e. vector) can be used to store a set.

A class that is used to represent a set could have the following instance methods:

```   Set();
Set(int capacity);
boolean isMember(Object element);
boolean isEmpty();
boolean isSubset(Set other);
int size();
Set union(Set other);
Set intersection(Set other);
Set difference(Set other);
void remove(Object element);
void clear();
```

{TopOfPage} {Oracle.com::API Specification | Tutorial} {Additional Resources}

Stacks

A  stack  is a data structure in which all access is restricted to the most-recently-inserted elements (LIFO: Last-In-First-Out).

My favorite real world example of a stack is a salad bar. Typically, at the start of the salad bar line is a stack of plates and normally you take the top-most plate (unless it is dirty or has some type of foreign looking object on it, in which case you dig down and take a plate from somewhere lower in the stack [atypical stack behavior]). In actualality, a stack is the wrong way to store plates at a salad bar because of the following scenario: The dishwasher cleans the dirty plates, brings them out front to the salad bar, and  pushes  them on top of the stack -- now John Q. Customer comes up and is stuck using a hot plate.

A stack has three natural operations: insert, delete, and find; but in stack terminology these operations are called  push ,  pop  and  top .

Elements are inserted onto a stack by using a push operation.

Elements are deleted from a stack by using a pop operation.

The most-recently inserted element can be examined by using a top operation.

Stacks are heavily used in system software (e.g. compilers). A stack can be used to check for unbalanced symbols (e.g. (), {}, []). Example algorithm:

1. create an empty stack
1. if the symbol is an opening symbol, push it onto the stack
2. if the symbol is a closing symbol and the stack is empty, then report an error
3. otherwise, pop the stack (if symbol popped is not the corresponding opening symbol, then report an error)
3. at EOF, if stack is *not* empty, then report an error

A stack is used to implement function (method) calls in most languages. For example in C++, when a function is called, memory for parameters and locally defined variables is allocated from the stack. When the function returns, the memory for the parameters and local variables is de-allocated from the stack. In addition, "jump" information and return value data is stored on the stack.

Stacks are also used in the evaluation of expressions (e.g. operator precedence parsing).

{TopOfPage} {Oracle.com::API Specification | Tutorial} {Additional Resources}

Queues

A  queue  is a data structure in which all access is restricted to the least-recently-inserted elements (FIFO: First-In-First-Out).

Operations are:

• `enqueue` -- insert at the back of the line (append)
• `dequeue` -- remove from the front of the line
• `front` -- access item from front of the line

Examples of a queue: buffered input and a line printer spooler.

Another queue example: message queues.

{TopOfPage} {Oracle.com::API Specification | Tutorial} {Additional Resources}