22 Feb 2012

The past couple classes we went over recursion, both in terms of an individual (static) method, and within instance methods.

Here are the static examples we went over:

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));
}
}


And here are our examples of some simple classes that use recursion.

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);
}

}


And a (not finished) binary tree:

/** 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);
}
}
}


If you take a course on data structures, you'll spend lots of time implementing better versions of those.