Search code examples
c++arraysalgorithmrecursionmultipath

Finding largest value in array using recursion

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: enter image description here

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

Solution

  • 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;
}