Home Previous Next

CSC205::Lecture Note::Week 04
Assignments | Code | Handouts | Resources | Email Thurman | Tweets::@compufoo
GDT::Bits:: Time  |  Weather  |  Populations  |  Special Dates

Overview Assignment(s)[program] #BitOperators [due 2/25/2017]

Code { [last week] Robot.java | [this week] Robot2.java } A.java (arrays) | XYZ.java
[recursion] Factorial.java | Power.java | PrintLD.java | Reverse.java | Fibonacci.java | GCD.java
[exceptions] Exceptions.java | TestExceptions.java | Rot13.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.

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.

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} {Derek Banas Videos}


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:

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:

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} {Derek Banas Videos}


Home Previous Next