I. Recursion and induction
   A. Introduction
      1. Textbook references
         a. for the material in this lecture, see Weiss Sections 7.1-7.3 and 
            Section 17.4 (yes, that's "seventeen")
      2. What is recursion?
         a. we say that a definition is {\bf recursive} when the entity being 
            defined is referred to in the definition itself; in the context of 
            Computer Science, the "entity" is often a function or data structure
      3. Philosophical and theoretical issues
         a. it is not obvious in all cases that a definition which refers to 
            itself makes any sense; it may be vacuous (consider, e.g., Laurie 
            Anderson's song "Let x = x")
      4. Recursive and base cases
         a. a "good" (i.e., non-vacuous) recursive definition usually involves 
            some notion of case distinction (e.g., "if-then-else") which 
            distinguishes between continued self-reference  (the recursive case) 
            and an atomic case which "grounds" the definition (the base case)
      5. Recursing through successive stages
         a. intuitively, we can think of a recursive definition as starting at some 
            point and preogressing, via self-reference, through a series of similar 
            stages until it reaches the base case, where it finally terminates
   B. Recursion versus loops
      1. Recursion versus loops
         a. under the view described above, recursion in algorithms clearly 
            provides something akin to a loop: a certain stage is repeated multiple 
            times until it stops
      2. Theoretical equivalence
         a. it turns out we can prove that recursion and while loops are equivalent 
            in expressive power, given some reasonable, minimal language context 
            including variables and assignments
      3. Advantages of recursion
         a. in many cases, recursive algorithms are more concise
         b. if the reader is familiar with recursion, recursive algorithms are 
            usually easier to understand
      4. Disadvantages of recursion
         a. recursion can cost more in terms of time and space
         b. if the reader is not familiar with recursion, it can be harder to
            understand
   C. Some recursive functions
      1. Example I: factorial
			factorial(0) = 1
			factorial(n) = n * factorial(n-1)
      2. Example II: Fibonacci numbers
      3. Example III: Ackermann/Buck function
   D. Inductive proofs
      1. Recursive definitions and inductive proofs
      2. Base case and inductive case
      3. Justifying inductive proof
      4. An example: factorials are positive
   F. Recursive tree traversals
      1. Recursive definition of binary trees
      2. Iterating through a tree
      3. Some code for recursive traversals
			    void printPreOrder( )
			    {
			        System.out.println( element );       // Node
			        if( left != null )
			            left.printPreOrder( );           // Left
			        if( right != null )
			            right.printPreOrder( );          // Right
			    }
			
			
			    void printPostOrder( )
			    {
			        if( left != null )
			            left.printPostOrder( );          // Left
			        if( right != null )
			            right.printPostOrder( );         // Right
			        System.out.println( element );       // Node
			    }
			
			    void printInOrder( )
			    {
			        if( left != null )
			            left.printInOrder( );            // Left
			        System.out.println( element );       // Node
			        if( right != null )
			            right.printInOrder( );           // Right
			    }