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.
• 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.

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.