Problem Statement

Write a program that finds the minimum and maximum elements of an array using recursion.

Examples

Example 1:

Input: arr = [1, 4, 3, -6, -4, 8, 7]
Output: min = -6, max = 8

Example 2:

Input: arr = [1, 1, 4, 10, 10, -4, -4]
Output: min = -4, max = 10

Problem Understanding

To solve this problem recursively, we need to understand that finding the minimum and maximum elements of an array involves comparing elements pairwise and updating the minimum and maximum values accordingly.

Recursion involves breaking down a problem into smaller instances until reaching a base case. In this case, the base case occurs when the array contains only one element, at which point we return that element as both the minimum and maximum.

Different Approaches

1️⃣ Recursion

Code:

#include <iostream>
#include <climits>

// Recursive function to find the minimum and maximum elements in an array
void findMinMax(int arr[], int start, int end, int& min, int& max) {
    // Base case: If the array contains only one element
    if (start == end) {
        min = max = arr[start];
        return;
    }

    // Base case: If the array contains only two elements
    if (end - start == 1) {
        min = std::min(arr[start], arr[end]);
        max = std::max(arr[start], arr[end]);
        return;
    }

    // Recursive case: Divide the array into two halves and find min/max in each half
    int mid = start + (end - start) / 2;
    int leftMin, leftMax, rightMin, rightMax;
    findMinMax(arr, start, mid, leftMin, leftMax);
    findMinMax(arr, mid + 1, end, rightMin, rightMax);

    // Combine the results from the two halves
    min = std::min(leftMin, rightMin);
    max = std::max(leftMax, rightMax);
}

int main() {
    int n;

    // Prompt the user to enter the size of the array
    std::cout << "Enter the size of the array: ";
    std::cin >> n;

    // Create an array of size n
    int arr[n];

    // Prompt the user to enter the elements of the array
    std::cout << "Enter the elements of the array:\n";
    for (int i = 0; i < n; ++i) {
        std::cin >> arr[i];
    }

    int min, max;

    // Call the recursive function to find the minimum and maximum elements
    findMinMax(arr, 0, n - 1, min, max);

    // Print the minimum and maximum elements
    std::cout << "Minimum element: " << min << std::endl;
    std::cout << "Maximum element: " << max << std::endl;

    return 0;
}

Complexity Analysis

Time Complexity:

• At each level of recursion, the array is divided into two halves, resulting in time complexity of O(log n).
• At each level, we perform a constant amount of work (comparing elements and updating min/max), which can be considered O(1).
• Therefore, the overall time complexity of the solution is O(log n) * O(1) = O(log n), where n is the size of the array.

Space Complexity:

• The space complexity of the solution is O(log n) as well, considering the recursive calls create a call stack with log(n) times.

2️⃣ Recursive 2

Code:

#include <iostream>

using namespace std;

int minElement(int arr[], int start, int size) {
    if(start == size) {
        return 0;
    }
    
    return min(arr[start], minElement(arr, start + 1, size));
}

int maxElement(int arr[], int start, int size) {
    if (start == size) {
        return 0;
    }
    
    return max(arr[start], maxElement(arr, start + 1, size));
}

int main() {
    int arr[] = {1, 4, 3, -5, -4, 8, 6};
    int size = sizeof(arr)/sizeof(arr[0]);
    cout << minElement(arr, 0, size) << endl;;
    cout << maxElement(arr, 0, size);
}

Output:

-5
8