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

• 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