Finding largest value in array using recursion

Question

I've been studying to ' Data Abstraction and Problem Solving with C++ ' book at recently, however i did stuck at some point.

I'm at recursion chapter, and i faced with a problem which is ' Finding largest value in an array'. As you know i have to solve this problem with recursion perspective and actually i already solved that with this algorithm ;

Which is basically, start from first item to last item of an array and algorithm is comparing every value with each other and in the and largest item of array stands alone in array(which is invoking the base case)

int largestValue(int anArray[], int first , int last){
int value;

// base case
if(first == last){
    value = anArray[first];
}
else if(anArray[first]>anArray[first+1]){
    anArray[first + 1] = anArray[first];
    value = largestValue(anArray, first + 1, last);
}else{ // anArray[first] < anArray[first + 1]
    value = largestValue(anArray, first + 1, last);
}
return value;

BUT , after i read the description of problem, it is said ' you have to solve this problem with multipath recursion.' For better understanding i'm putting screenshot of problem:

And i couldn't figured out algorithm with ' Multipath Recursion ' perspective.

Answer 1

I would recommend you use a helper function that calls your largestvalue function like so:

int largestValue(int arr[], int size){
    int middle = (size - 1)/2;
    int first_max = largestValue(arr, 0, middle);
    int second_max = largestValue(arr, middle + 1, largest - 1);
    if(first_max < second_max){
       return second_max;
    }
    return first_max;
}

Answer 2

Split the array in the middle, then call the function for each half:

template<class Random_it>
// typename std::iterator_traits<Random_it>::value_type
auto recursive_max(Random_it first, Random_it last) {
    assert(first != last);
    if (last - first == 1)
        return *first;
    const auto mid = first + (last - first) / 2;
    const auto l_max = recursive_max(first, mid);
    const auto r_max = recursive_max(mid,   last);
    return (r_max > l_max) ? r_max : l_max;
}

Usage example:

std::vector<int> vec{/* init values */};
const auto max = recursive_max(vec.begin(), vec.end());

Demo

Note that here first and last represent a half-open interval [first, last), in agreement with a convention that is widely used in the C++ standard library.

Answer 3

The recursive algorithm just splits the array in two and finds the largest value recursively, then compares the two and returns the highest. What you need to do is to use the boundaries first and last which tell you which part of the array to calculate the largest value of.

A simple solution would be the following:

int largestValue(int anArray[], int first, int last) {
    if (first == last) {
        return anArray[first];
    }
    int middle = (first+last)/2;
    int left = largestValue(anArray, first, middle);
    int right = largestValue(anArray, middle+1, last);
    int max;
    if (left > right) {
        max = left;
    } else {
        max = right;
    }
    return max;
}