ISC Practicals and Theory - Array Sum and Maximum (Recursive Technique)

The sum of an array and its largest element can both be found by recursion. Each recursive method handles one element and leaves the rest of the array to a call of itself: sum() adds the element to the sum of the rest, and max() compares the element with the maximum of the rest.

Definition

For an array a of n elements, the sum from index i is defined as:

• $0$ when i == n (no elements left)
• a[i] plus the sum from index i + 1 otherwise

The maximum from index i is defined as:

• a[i] when i == n - 1 (one element left)
• the larger of a[i] and the maximum from index i + 1 otherwise

For {4, -8, 15, 8, 3}: the sum is $4 - 8 + 15 + 8 + 3 = 22$ and the maximum is $15$.

The program uses two separate recursive methods, sum() and max(), each doing one job. The array holds 1 to 20 elements. A size of 0 is rejected because an empty array has no maximum.

Algorithm

1. main() creates an object ob of class ArraySum; the constructor creates the array and sets n = 0.
2. input() reads n. If it is less than 1 or more than 20 it returns false and main() prints the invalid size message.
3. Otherwise input() reads the n elements into a[] and returns true.
4. sum(0):
   • Base case: if i == n, return 0.
   • Recursive case: return a[i] + sum(i + 1).
5. max(0):
   • Base case: if i == n - 1, return a[i].
   • Recursive case: store max(i + 1) in m; return a[i] if it is greater than m, otherwise return m.
6. main() prints the sum and the maximum.

Program

input() accepts the data, sum() and max() are the two recursive methods.

import java.util.Scanner;

/**
 * Class ArraySum finds the sum and the maximum of an integer array
 * using recursion.
 */
public class ArraySum
{
    int a[];    // array that stores the numbers entered by the user
    int n;      // number of elements actually stored in the array

    /**
     * Default constructor: creates the array and initialises n.
     */
    ArraySum()
    {
        a = new int[20];  // array can hold at most 20 elements
        n = 0;
    }

    /**
     * Accepts the size and the elements from the user.
     * Parameter sc: Scanner used to read from the keyboard.
     * Return type: boolean, true if the size is valid (1 to 20), otherwise false.
     */
    boolean input(Scanner sc)
    {
        System.out.print("Enter the number of elements (1 to 20): ");
        n = sc.nextInt();
        if (n < 1 || n > 20)      // size outside the allowed range
            return false;
        System.out.println("Enter the elements:");
        for (int i = 0; i < n; i++)   // read the elements one by one
            a[i] = sc.nextInt();
        return true;
    }

    /**
     * Recursively finds the sum of the elements from index i to the end.
     * Parameter i: index from which the sum is required.
     * Return type: int, sum of a[i] to a[n-1].
     */
    int sum(int i)
    {
        if (i == n)               // base case: no element left, sum is 0
            return 0;
        return a[i] + sum(i + 1); // recursive case: a[i] plus sum of the rest
    }

    /**
     * Recursively finds the largest element from index i to the end.
     * Parameter i: index from which the maximum is required.
     * Return type: int, largest of a[i] to a[n-1].
     */
    int max(int i)
    {
        if (i == n - 1)           // base case: only one element left
            return a[i];
        int m = max(i + 1);       // recursive case: maximum of the rest
        if (a[i] > m)             // compare a[i] with the maximum of the rest
            return a[i];
        return m;
    }

    /**
     * main method: creates the object and calls the methods.
     */
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);   // reads input from the keyboard
        ArraySum ob = new ArraySum();          // object of the class
        if (ob.input(sc))
        {
            System.out.println("Sum = " + ob.sum(0));
            System.out.println("Maximum = " + ob.max(0));
        }
        else
            System.out.println("Invalid size. Size must be between 1 and 20");
    }
}

Variable description table

Sample input and output

Enter the number of elements (1 to 20): 5
Enter the elements:
4 -8 15 8 3
Sum = 22
Maximum = 15

Enter the number of elements (1 to 20): 3
Enter the elements:
-5 -2 -9
Sum = -16
Maximum = -2

Enter the number of elements (1 to 20): 1
Enter the elements:
-9
Sum = -9
Maximum = -9

Enter the number of elements (1 to 20): 0
Invalid size. Size must be between 1 and 20

Dry run

Input: n = 5, elements 4 -8 15 8 3. Calls go down to the base case; the values come back up.

Reading the table from the bottom, sum(5) returns 0, sum(4) returns 3, sum(3) returns 11, sum(2) returns 26, sum(1) returns 18 and sum(0) returns 22.

max(4) returns 3 first, then max(3) returns 8, max(2) returns 15, and max(1) and max(0) keep 15. The output is Sum = 22 and Maximum = 15.

Variations

1. Recursive sum only "Write a program to find the sum of the elements of an array using recursion."
2. Minimum element "Write a program to find the smallest element of an array using recursion."
3. Average "Write a program to find the average of the elements of an array using a recursive sum."
4. Count even numbers "Write a program to count the even numbers in an array using recursion."