Home Previous Next

CSC205::Lecture Note::Week 07
Assignments | Code | Handouts | Resources | Email Thurman { compufoo::Twitter | Facebook | YouTube}
GDT::Bits:: Time  |  Weather  |  Populations  |  Special Dates

Overview Assignment(s):  Code[interface] CSC205_Containers
[recursion] Factorial.java {Factorial2.java} | Power.java | PrintLD.java | Reverse.java | Fibonacci.java | GCD.java {GCDverbose.java}
[list data structure] IntList.java [code base for the IntList assignment]


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}


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.

Some final comments:

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.

Programming Loops vs Recursion - Computerphile

What on Earth is Recursion? - Computerphile

Spiked Math Comics

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}


Data structures are coming...

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:

List operations include:

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:

Example of sets:

The following operations are performed on 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 add(Object element);
   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
  2. read symbols until EOF
    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:

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

Another queue example: message queues.

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


Home Previous Next