CS211 Spring 2002
Lecture 5: Recursion
2/4/2003
-------------------------------------------------------------------------------
0)  Announcements:
    + Just added? See http://www.cs.cornell.edu/courses/cs211/2003sp/
                  Read syllabus! Do everything in "What To Do First"!!!
    + need for programming demo this weekend? (see online announcement)
      (I need to know if people will go)

    Objectives/Topics of Lecture 5:
    + wrapup of L4 (induction)
    + intro to recursion (maybe starts on Tues)
    + parsing

    Credits
    + I'm borrowing massively from KP's CS211 notes, the course texts,
      a few handbooks, and various on-line notes, including my own :-)
-------------------------------------------------------------------------------
1) Recursion Reminder

   Factorial: 

      iterative:  n! = 0*1*2...*(n-1)*n

                         [ 1, if n=0
      functional: f(n) = [  
                         [ n*f(n-1), if n>0

      how to express functional?      

      n == 0:   if (n==0), then return 1
      n == 1:   return 1*f(1-1)
      n == 2:   return 2*f(2-1)
      ... 
      n == k:   return k*f(k-1)

   Connection to induction?

      + you know that f(0) =  
      + you know that f(n) = 


   Code (revisted)

      // Precondition: n is a nonneg integer
      // Postcondition: n! is generated and returned

         public int factorial(int n ) {
 
	    if ( ________ ) return ________ ;

            else return ____________________________________

         } // Method factorial

   Things to note:

      + computational path is "two-way": 
        first breaks problem down, second assembles solution
      + recursion solves complex problems by breaking things into simple steps
      + recursive definition: basecases (when to stop) and recursive steps
                              (how to break into known operations)
-------------------------------------------------------------------------------
2) Tracing: Frames and Activation Records

   Some "guts":

     + Program keeps track of function calls
     + Each function has its own ACTIVATION RECORD (local vars, values, ops)
       (also called a STACK FRAME)
     + Frames are stored in RUN-TIME STACK (or just "THE STACK")
     + As a function starts, it's added to the stack (starts at bottom)
     + As a function finishes, it's "popped" off the stack

   See also Chap 10, p311-313 in DS&SD
     
   Factorial example:





















-------------------------------------------------------------------------------
3) Another Example

   Simple powers:

     iter: v^p = v*v*... (p times)
     func: power(v,0) = 1 (base case)
           power(v,p) = v*power(v,p-1) (recursive step)

   Code for simple powers:

      public class power1 {

         public static void main(String[] args) {

	    int val = Integer.parseInt(args[0]);
            int pow = Integer.parseInt(args[1]);
	    System.out.println(power(val,pow));
         }

      public static int power(int x, int p) {
	 if (p==0) return 1;
	 else return x*power(x,p-1);
      }
   }

-------------------------------------------------------------------------------
   Better powers:
  
     ex) 2^4 = (2^2) * (2^2)
         2^8 = (2^4) * (2^4) = (2^2) * (2^2) *(2^2) * (2^2)
  
         2^3 = (2^2) * (2^1)
         2^5 = (2^4) * (2^1) = (2^2) * (2^2) * (2^1)

         if p is zero, v^p = 1 (BC)
         if p is non-zero and even, v^p = (v^(p/2))^2 
         if p is odd, v^p = (v^(p/2))^2 * v
 
   Code for better powers:

      public static int betterPower(int v, int p) {
	  if (p==0) return 1;
	  else if (p % 2 == 0) return betterPower(v, p/2)*betterPower(v, p/2);
	  else return betterPower(v, p/2)*betterPower(v, p/2)*v;
      }

      OR
 
      public static int betterPower(int v, int p) {
  	  if (p==0) return 1;
	  else {
	     int evenPower = betterPower(v, p/2)*betterPower(v, p/2);
	     if (p % 2 == 0) return evenPower;
	     else return evenPower*v;
	  }	
      }
-------------------------------------------------------------------------------
4) Fibonacci Numbers

   http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibnat.html
-------------------------------------------------------------------------------
5) Recursive List Methods

   Recursive definition of a list:
     + a list is empty: []
     + a list has a head and tail [H|T], where tail is a list

   Base cases:
     + usually empty list, 1-elem list
    
   Recursive step:
     + break into sublists
     + send tail back as "the new list" and recurse with that















-------------------------------------------------------------------------------
public class MyVector {
    private MyVector next;
    private Integer value;
    private int index;
    private static int size;

    public MyVector(Integer i, MyVector next) {
	value = i;
	this.next = next;
	index=size;
	size++;
    }

    public Integer getElement() {
        return value;
    }

    public void setNext(MyVector elem) {
        next = elem;
    }

    public MyVector getNext() {
	return next;
    }

    public static int getSize() {
	return size;
    }

    public String toString() {
        return value.toString();
    }

    public int toValue() {
        return value.intValue();
    }
}

























-------------------------------------------------------------------------------