Write a recursive function called sumArray() that determines the sum of the inte

Question

Write a recursive function called sumArray() that determines the sum of the integers in an array
A[0...n-1]. Do this in 3 ways.
a. Recur on A[0...n-2], add the result to A[n-1], then return the sum.
b. Recur on A[1...n-1], add the result to A[0], then return the sum.
c. Split A[0...n-1] into two subarrays of length (approximately) n/2, recur on the two subarrays, add
the results and return the sum. Hint: think about MergeSort().
4. Write a modification of the recursive function BinarySearch() that prints out the sequence of array
elements that are compared to the target.
5. What output does the following program produce?
public class problem5 {
public static int getValue(int a, int b, int n){
int x, c;
System.out.println("arrive: a = " + a + " b = " + b);
c = (a+b)/2;
if( c*c <= n ){
x = c;
}else{
x = getValue(a, c-1, n);
}
System.out.println("depart: a = " + a + " b = " + b);
return x;
}
public static void main(String[] args){
System.out.println(getValue(3, 13, 5));
}
}

Explanation / Answer

import java.util.Arrays;

class Main {
// first method to do it with A[0...n-2]
public static int recOne(int[] a)
{
if(a.length == 1)
return a[0];
  
// each time adding the last number
return a[a.length-1] + recOne(Arrays.copyOfRange(a, 0, a.length-1));
}
  
// second method to do it with A[1...n-1]
public static int recTwo(int[] a)
{
if(a.length == 1)
return a[0];
  
// each time adding the first number
return a[0] + recOne(Arrays.copyOfRange(a, 1, a.length));
}
  
public static int recThree(int[] a)
{
if(a.length == 1)
return a[0];
  
// each time making it half and then adding both the results
int mid = a.length/2;
return recThree(Arrays.copyOfRange(a, 0, mid)) + recThree(Arrays.copyOfRange(a, mid, a.length));
}
  
// driver
public static void main(String[] args) {
System.out.println("First one: "+recOne(new int[] {1,2,3,4,7}));
System.out.println("Second One: "+recTwo(new int[] {1,2,3,4,6}));
System.out.println("Third One: "+recThree(new int[] {1,2,3,4,5,6}));
}
}

/*SAMPLE OUTPUT
First one: 17
Second One: 16
Third One: 21
*/

/*NOTE: One complete question at a time please -- Chegg Policy*/

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.