CSC 185 & 201: Spring 2012

public class RecursionExamples {
    
    // Compute x! = 1 × 2 × ... × x
    public static int factorial(int x) {
        if (x == 0)
            return 1;
        int fact = x * factorial(x - 1);
        return fact;
    }
    
    // Compute the nth Fibonacci number (wastefully!)
    public static int fib(int n) {
        System.out.println("fib:" + n);
        if (n == 1 || n == 2) 
            return 1;
        int fn = fib(n-1) + fib(n - 2);
        System.out.println("fib returning:" + n);
        return fn;
    }
    
    // Iterative version that is much faster
    public static int fibBetter(int n) {
        int a = 1;
        int b = 1;
        if (n < 3)
            return 1;
        for (int i = 3; i <= n; i++) {
            int tmp = b;
            b = a + b;
            a = tmp;
        }
        return b;
    }
    
    // Compute base to the exp power
    public static int powIterative(int base, int exp) {
        int prod = 1;
        for (int i = 0; i < exp; i++) {
            prod *= base;
        }
        return prod;
    }
    
    // Compute base to the (integral) exp power recursively,
    // using the fact that x^(2n) = (x^n)^2, and
    // x^(2n+1) = x(x^n)^2
    public static int pow(int base, int exp) {
        if (exp == 1)
            return base;
        // Note: integer division rounds exp down if odd
        int half = pow(base, exp/2);
        // If odd, must include one extra multiple of base
        if ((exp % 2) == 1) 
            return base * half * half;
        else
            return half * half;
    }
    
    public static void main(String[] args) {
        int x = pow(5, 11);
        System.out.println(x);
        System.out.println(Math.pow(5, 11));
    }
}

import java.util.Random;


/** Simple linked list example.
 * 
 * @author fsjlepak
 */
public class List {
    public int data;  // Number stored in each link
    public List next; // Points to next link in the list
    
    public List(int data, List next) {
        this.data = data;
        this.next = next;
    }
    
    public String toString() {
        // Convert first link to string, then 
        // recursively convert rest to string.
        
        // Base case:
        if (next == null)
            return "" + data;
        
        return data + ", " + next.toString();
    }
    
    // Compute total length of list
    public int length() {
        if (next == null)
            return 1; 
        return 1 + next.length();
    }

    // Iterative version
    public int lengthNonRecursive() {
        int count = 1;   // Number of links seen so far
        List loc = this; // Keep track of current link
        // Travel until there's no next link to move to
        while (loc.next != null) {
            count++;
            loc = loc.next;
        }
        return count;
    }
    
    // Compute sum of all link data
    public int sum() {
        if (next == null)
            return data; 
        return data + next.sum();
    }
    
    /** Insert element in sorted (ascending) order.
     *  Assume existing list is sorted.
     *  
     * @param x element to insert
     */
    public void insert(int x) {
        // x is the new largest element, and we're at the end of the list
        if (x >= data && next == null) {
            // make a new link for x and put it at the end
            next = new List(x, null);
        }
        // x is the new smallest element
        else if (x < data) {
            // Bump the current data value down to a new next link, 
            // and update next to point to the new link
            next = new List(data, next);
            // Put x in the data slot for the current link
            data = x;

            // Example: if the list looks like
            //  +-----+           +-----+
            //  |  5  |---------->|  6  |
            //  +-----+           +-----+
            // and we call insert(1), the result is:
            //  +-----+  +-----+  +-----+
            //  |  1  |->|  5  |->|  6  |
            //  +-----+  +-----+  +-----+
            // The 1 replaced the 5, and the 5 resides in the new link
            
        }
        // x is somewhere in the middle
        else {
            // just move on to the next link and try to insert there
            next.insert(x);
        }
    }
    
    public static void main(String[] args) {
        List one = new List(1, null);
        List a = new List(1, new List(2, new List(3, null)));
        System.out.println(a);
        
        // Test insert() by inserting a bunch of random values
        Random rand = new Random();
        List r = new List(0, null);
        for (int i = 0; i < 20; i++)
            r.insert(rand.nextInt(50));
        System.out.println(r);
    }
    
}

/** Simple and incomplete binary tree example.
 */
public class BinaryTree {
    public int data;
    public BinaryTree left;
    public BinaryTree right;

    public BinaryTree(int data, BinaryTree left, BinaryTree right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
    
    // Determine if value x is contained in the tree, assumed it was
    // constructed correctly -- all entries in left branch must be
    // smaller than the root, and all entries in the right branch
    // must be larger.
    public boolean find(int x) {
        // Handle 3 cases: equal, smaller, or larger.
        if (x == data) {
            return true;
        } else if (x < data) {
            // If left branch is empty (null), then x is not in tree
            if (left == null)
                return false;
            else // Otherwise, recursively search the left branch
                return left.find(x);
        } else {
            // Same logic, with right replacing left
            if (right == null)
                return false;
            else
                return right.find(x);
        }
    }
}