Finding Minimum, Maximum Element from an Array using Recursion

Problem Statement

Given an array of integers arr, find the minimum and maximum element of this array using recursion.

Examples

Example 1:

Input: arr = {1, 4, 3, -5, 7, 5}

Output: min = -5, max = 7

Different Recursive Approaches

Approach 1:

Code Implementation in C++:

#include <iostream> 
using namespace std; 
  
// function to print Minimum element using recursion 
int findMinRec(int A[], int n) 
{ 
    // if size = 0 means whole array has been traversed 
    if (n == 1) 
        return A[0]; 
    return min(A[n-1], findMinRec(A, n-1)); 
}

// function to return maximum element using recursion 
int findMaxRec(int A[], int n) 
{ 
    // if n = 0 means whole array has been traversed 
    if (n == 1) 
        return A[0]; 
    return max(A[n-1], findMaxRec(A, n-1)); 
}
  
// driver code to test above function 
int main() 
{ 
    int A[] = {1, 4, 45, 6, -50, 10, 2};
    int n = sizeof(A)/sizeof(A[0]);
    cout <<  findMinRec(A, n)<< endl;
    
    
cout <<  findMaxRec(A, n)<<endl;
    return 0; 
}

Complexity Analysis:

• Time Complexity:O(n)
  • Since each element if visited exactly once.
• Space Complexity:O(n)
  • Due to the recursion stack.

2 Approach: Divide and Conquer

Code Implementation in C++:

#include <iostream> 
using namespace std; 
  
// function to find Minimum element using divide and conquer
int findMin(int A[], int low, int high) 
{ 
    if (low == high) // if there is only one element
        return A[low]; 
  
    int mid = (low + high) / 2; // find the mid index
  
    // divide the array into two halves and recursively find the minimum in each half
    int leftMin = findMin(A, low, mid); 
    int rightMin = findMin(A, mid + 1, high); 
  
    // return the minimum of leftMin and rightMin
    return min(leftMin, rightMin); 
} 

// function to find Maximum element using divide and conquer
int findMax(int A[], int low, int high) 
{ 
    if (low == high) // if there is only one element
        return A[low]; 
  
    int mid = (low + high) / 2; // find the mid index
  
    // divide the array into two halves and recursively find the maximum in each half
    int leftMax = findMax(A, low, mid); 
    int rightMax = findMax(A, mid + 1, high); 
  
    // return the maximum of leftMax and rightMax
    return max(leftMax, rightMax); 
} 
  
// driver code to test above functions 
int main() 
{ 
    int A[] = {1, 4, 45, 6, -50, 10, 2}; 
    int n = sizeof(A)/sizeof(A[0]); 
    
    cout << "Minimum Element: " << findMin(A, 0, n - 1) << endl; 
    cout << "Maximum Element: " << findMax(A, 0, n - 1) << endl; 
    
    return 0; 
}

Complexity Analysis:

• Time Complexity:O(n)
• Space Complexity:O(log n)
  • Since at each level, the array is divided into two halves.