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

This version finds the sum and the largest element of an array with two recursive methods inside a class that has a parameterised constructor. sum() adds the current element to the sum of the rest; max() compares the current element with the maximum of the rest.

Definition

For an array of n elements, the sum from index i is $0$ when i == n, otherwise a[i] plus the sum from i + 1. The maximum from index i is a[i] when i == n - 1, otherwise the larger of a[i] and the maximum from i + 1. For {4, -8, 15, 8, 3} the sum is $22$ and the maximum is $15$.

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

Algorithm

1. main() reads size. If it is less than 1 or more than 20, it prints the invalid size message and stops.
2. main() creates the object with new ArraySum(size); the constructor stores n and creates the array a of n elements.
3. readArray() reads the n elements.
4. sum(0): return 0 if i == n, else return a[i] + sum(i + 1).
5. max(0): return a[i] if i == n - 1; else take m = max(i + 1) and return the larger of a[i] and m.
6. display(s, m) prints the sum and the maximum.

Program

The constructor creates the array, readArray() fills it, sum() and max() are recursive, display() prints.

import java.util.Scanner;

/**
 * Class ArraySum finds the sum and the maximum of an integer array
 * using recursion. The array is stored by a parameterised constructor.
 */
public class ArraySum
{
    int a[];    // array that stores the numbers
    int n;      // size of the array

    /**
     * Parameterised constructor: creates the array of the given size.
     * Parameter size: number of elements.
     */
    ArraySum(int size)
    {
        n = size;
        a = new int[n];       // array of exactly n elements
    }

    /**
     * Reads the n elements of the array.
     * Parameter sc: Scanner used to read from the keyboard.
     */
    void readArray(Scanner sc)
    {
        System.out.println("Enter the elements:");
        for (int i = 0; i < n; i++)   // read the elements one by one
            a[i] = sc.nextInt();
    }

    /**
     * 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;
    }

    /**
     * Displays the sum and the maximum.
     * Parameters s and m: the sum and the maximum already calculated.
     */
    void display(int s, int m)
    {
        System.out.println("Sum = " + s);
        System.out.println("Maximum = " + m);
    }

    /**
     * main method: reads and validates the size, creates the object
     * and calls the methods.
     */
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);   // reads input from the keyboard
        System.out.print("Enter the number of elements (1 to 20): ");
        int size = sc.nextInt();               // size of the array
        if (size < 1 || size > 20)             // size outside the allowed range
        {
            System.out.println("Invalid size. Size must be between 1 and 20");
            return;
        }
        ArraySum ob = new ArraySum(size);      // object of the class
        ob.readArray(sc);
        int s = ob.sum(0);                     // recursive sum from index 0
        int m = ob.max(0);                     // recursive maximum from index 0
        ob.display(s, m);
    }
}

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): 1
Enter the elements:
-9
Sum = -9
Maximum = -9

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

Dry run

Input: size = 5, elements 4 -8 15 8 3. The calls go down to the base case and the values return up.

The returns happen from the bottom: 0, 3, 11, 26, 18, 22, so s = 22.

The returns happen from the bottom: 3, 8, 15, 15, 15, so m = 15. display(22, 15) prints 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."