CSC212 Lab 9 2014

--D. Thiebaut (talk) 15:00, 22 October 2014 (EDT)

---

...

Recursion

• Use the skeleton program below to write different recursive functions.

public class RecurseSkeleton {

	private static int[] initSortedArray( int N ) {
		int[] array = new int[N];
		array[0] = 3;
		for ( int i=1; i<N; i++ ) 
			array[ i ] = array[i-1] + (i*11)*7;
		
		return array;
	}
	
	private static int[] initArray( int N ) {
		int[] array = new int[N];
		array[0] = 3;
		for ( int i=1; i<N; i++ ) 
			array[ i ] = (i+1) * 101 % 23;
		
		return array;
	}
	
	private static int fact( int n ) {
		// stopping condition
		if ( n==1 ) 
			return 1;
		
		// recursive step
		return n * fact( n-1 );
	}
	
	public static void main(String[] args) {
		int N = 20; 
		int A[] = initArray( N );

		int x, y;
		x = 5;
		
		System.out.println( "fact( " + x + " ) = " + fact( x ) );
	}
}

Problem 1

Sum

• Write a recursive function that will compute the sum of all the elements of the array, following this definition, where A[1:N] indicates the elements of the array going from Index 1 to Index N, included:

sum( array ) =

| 0 if length( array ) == 0

| array[0] if length( array )== 1

| array[0] + sum( array[1 : N-1] ), where N is the size of the array.

• Write a recursive function that will compute the sum of all the elements of the array, following this definition:

sum( array ) =

| 0 if length( array ) == 0

| array[0] if length( array )== 1

| array[N-1] + sum( array[0 to N-2] ), where N is the size of the array.

• Write a recursive function that will compute the sum of all the elements of the array, following this definition:

sum( array ) =

| 0 if length( array ) == 0

| array[0] if length( array )== 1

| sum( array[0 to mid] ) + sum( array[mid+1 to N-1] ), where N is the size of the array, and mid = N/2

Max

• Write a recursive function that finds the largest element of an array recursively:

max( array ) =

| array[0] if length( array )== 1

| largest of array[0] and max( array[1 : N-1] ), where N is the size of the array.

Binary Search

Implement Binary Search on a sorted array. The algorithm is simple:

• Main Program:

• Input: A sorted array of size N
• a key, of the same type as the elements of A
• index = binSearch( key, A, 0, N-1 ) // search the key in A, ranging from Index 0 to Index N-1

• binSearch( key, A, low, high )

• if low > high, end of search. Key not found. Return -1
• mid = (high+low) / 2
• if key in A[mid], then key found: return mid as index of key
• if key < A[mid], then key must be in lower part of array, from low to mid-1

index = binSearch( key, A, low, mid-1 )

• otherwise key > A[mid], then key must be in upper part of array, from mid+1 to high

index = binSearch( key, A, mid+1, high )

• return index

• Write the recursive binSearch function. Use the skeleton program introduce earlier, and make sure you initialize the array with sorted ints.
• Make sure it finds keys that are located at the beginning of the array, at the end, in the middle, or keys that are not in the array.

Counting the Number of Probes

• We refer to the action of looking at an element in an array as a probe.
• Create a static int counter in the class that holds your binary search function, and increment it every time your binSearch function looks at an element in your array. For example:

         counter++;
         if ( array[mid]==key )...

• Make sure you reset the counter to 0 in main(), before you start a search.
• Make your program print the index of where it finds (or not) the key, along with the number of probes required to find it.
• Set N, the dimension of the array, to 20.
• Run a few searches, and get a sense for the number of probes requires.
• Now, set N to 100, and perform a few searches. Look at how the number of probes changes, on the average.
• Set N to 1000. Same exercise.
• Set N to 10,000. Same exercise.
• Set N to 100,000. Same exercise.
• Set N to 1,000,000. Same exercise.
• Set N to 10,000,000. Same exercise.
• Set N to 100,000,000. Same exercise. Isn't it amazing how few probes are needed to search an an array of 100 million ints? That's the power of O( log(n) )!

RPN

• Here's a skeleton for a recursive Reverse-Polish-Notation solver:

import java.awt.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;

public class RecursiveRPN {
	
	private static int recurseSolve( ArrayList tokens, Stack<Integer> stack ) {
		// STOPPING CONDITION
                // if the size of the token list is 0, then empty expression: return top of stack
                
                //===> put your code here...

	        // get the next token from the array, the first one, and remove it from the array...	

                //===> put your code here...


 		// DO SOME WORK
                // if the token we got above is a "+", then pop 2 ints from stack, add them up, push sum back in stack.
                // similarly, if token is "-", pop 2, subtract, push difference
                // if token is "*", pop 2, multiply them together, push product
                // if token is "/", pop 2, divide 2 by first, push integer quotient back in stack...

                //===> put your code here...

                // and if token was not a +, -, *, or /, then it must be an int.  push it in the stack...
                // (and be careful, because a token is a string, and the stack holds integers only...)

		
                // RECURSIVE STEP: we've done some work, recurse and pass the remaining tokens and stack
                // to recurseSolve() 

                //===> put your code here...

                // return result...
                //  whatever we get back from recurseSolve, in the recursive step, we pass back...

                //===> put your code here...
	}

	
	static public void main( String[] args ) {
		ArrayList<String> tokens = new ArrayList<String>();
		
		// if user specifies expression on command line, then uses that
		if ( args.length != 0 ) {
			for ( int i=0; i<args.length; i++ )
				tokens.add( args[i].trim() );
		}
		// else use the expression below
		else {
			String expression = "3 5 + 7 3 - *";
			String[] tokenStrings = expression.split( " " );
			for ( int i=0; i<tokenStrings.length; i++ )
				tokens.add( tokenStrings[i] );
		}
		
		// display the tokens, for debugging purposes
		System.out.println( "tokens = " + tokens );
		
		// create a stack
		Stack<Integer> stack = new Stack<Integer>();
		
		// solve expression recursively
		int x = recurseSolve( tokens, stack );
		
		// display result.
		System.out.println( "result = " + x );
	}
}

• Study the comments left in recurseSolve(), and replace the "//===> put your code here" comments by java code implementing all the operations described.

• Verify that your program works and outputs 32.
• Modify the expression in main() and solve something a bit more complicated. Say, "12 34 56 + + 3 - 5 9 + * 10 /", which should evaluate to 138.