find the largest integer in the array with recursion

[medosz]

This program finds the largest interger in the array.
I am trying to understand it but I am struggling with the recursion.
For example in line 19:
max = recursiveMaximum(arr, first+1, last);
How can we put the argument with 3 elements in an integer?
Could someone explain the recursiveMaximum function step by step please? It would help a lot.

#include <iostream>
#include <array>
using namespace std;

int recursiveMaximum(array<int,10>, int, int);

int main(){
  const size_t arraySize{10};
  array<int, arraySize> array1{1,2,3,40,5,6,7,8,9,10};
  cout << recursiveMaximum(array1, 0, 9);
}

int recursiveMaximum(array<int,10> arr, int first, int last){
  int max;
  if(first == last){
  return arr[first];
  }
  
  max = recursiveMaximum(arr, first+1, last);
  if(arr[first]>max){
      return arr[first];
  }
  else{
     return max;
  }
}

[George P]

[misunderstood the question]

[Manga]

If we look at the function recursiveMaximum we see it has three possible return values.

int recursiveMaximum(array<int,10> arr, int first, int last){
  int max;
  if(first == last){
  return arr[first];
  }
  
  max = recursiveMaximum(arr, first+1, last);
  if(arr[first]>max){
      return arr[first];
  }
  else{
     return max;
  }
}

The first possible return value is return arr[first];. This return will happen if first is equal to last. This means we have reached the end of the array. Notice this return value happens before the recursive call to the function recursiveMaximum. If first is equal to last the recursive loop ends.

Next we get a value for the int max. We do this by calling our function recursiveMaximum, which returns a value at some point. But we increase the value of first by 1. Originally first had a value of 0 but now it is 1. Still no value is given to max yet because before a value is given we make another call to the function again. Now first has a value of 2. This cycle of calling our recursive function continues until we reach a point where first is equal to last, or 9 in this case. Now max is given its first value of arr[9], which equals 10. Now we have to start working our way backwards through all those function calls.

A comparison takes place. If arr[8] is > max, which is 10, then return arr[8] or else return max. Since max is equal to 10, the value of max is returned.

Now max still has a value of 10 and we work our way through the previous loop.
A comparison takes place. If arr[7] is > max, which is 10, then return arr[7] or else return max. Since max is equal to 10, the value of max is returned.

Now max still has a value of 10 and we work our way through the previous loop.
A comparison takes place. If arr[6] is > max, which is 10, then return arr[6] or else return max. Since max is equal to 10, the value of max is returned...

This working our way back through all those function calls continues until arr[3], which is equal to 40. The value of arr[3] is greater than 10 so arr[3] gets returned. Now max has a value of 40. And we continue through those function calls.

When all is done and we return to our original function call, max has a value of 40 and arr[0] has a value of 1. The int max is our final return value and the program ends with an output of 40.

[mbozzi]

int recursiveMaximum(std::array<int,10> a, int lb = 0)
{
  return (a.size() - lb) == 1? a[lb]: std::max(a[lb], recursiveMaximum(a, lb + 1)); 
}

[ne555]

> How can we put the argument with 3 elements in an integer?
¿ah?

> Could someone explain the recursiveMaximum function step by step please?
debugger, run step-by-step, watch the call stack

[lastchance]

#include <iostream>
#include <array>
#include <algorithm>
using namespace std;

template <typename T, size_t N> T recursiveMaximum( const array<T,N> &arr, int first, int last )
{
   if ( first == last ) return arr[first];
   int half = ( first + last ) / 2;
   return max( recursiveMaximum( arr, first, half ), recursiveMaximum( arr, half + 1, last ) );
}

int main()
{
   const size_t arraySize = 10;
   array<int, arraySize> array1 = { 1, 2, 3, 40, 5, 6, 7, 8, 9, 10 };
   cout << recursiveMaximum( array1, 0, 9 );
}

[dutch]

A tail recursive version.

#include <iostream>
#include <array>
using namespace std;

template<typename T, size_t N>
T recursiveMaximum(const array<T,N>& a, size_t i, T m)
{
    return i == N ? m : recursiveMaximum(a, i + 1, a[i] > m ? a[i] : m);
}

template<typename T, size_t N>
T recursiveMaximum(const array<T,N>& a)
{
    return recursiveMaximum(a, 1, a[0]);
}

int main(){
    array a {1, 2, 3, 40, 5, 6, 7, 8, 9, 10}; // C++17 can deduce type and size
    cout << recursiveMaximum(a) << '\n';
}

Or maybe:

#include <iostream>
#include <array>
using namespace std;

template<typename T, size_t N>
T recursiveMaximum(const array<T,N>& a, size_t i = 0, T m = 0)
{
    if (i == 0) m = a[0];
    return i == N ? m : recursiveMaximum(a, i + 1, a[i] > m ? a[i] : m);
}

int main(){
    array a {1, 2, 3, 40, 5, 6, 7, 8, 9, 10}; // C++17 can deduce type and size
    cout << recursiveMaximum(a) << '\n';
}

[dhayden]

When learning recursion, sometimes it helps to add code to show each entry and exit to/from the recursive function:

int recursiveMaximum(array<int,10> arr, int first, int last){
  int max;
  cout << "Entering recursiveMax(arr, " << first << ", " << last << ")\n";
  if(first == last){
  cout << "Leave recursiveMax(arr, " << first << ", " << last
       << "). Result = " << arr[first] << "\n";
  return arr[first];
  }
  
  max = recursiveMaximum(arr, first+1, last);
  if(arr[first]>max){
      cout << "Leave recursiveMax(arr, " << first << ", " << last
	   << "). Result = " << arr[first] << "\n";
      return arr[first];
  }
  else{
  cout << "Leave recursiveMax(arr, " << first << ", " << last
       << "). Result = " << max << "\n";
     return max;
  }
}

Entering recursiveMax(arr, 0, 9)
Entering recursiveMax(arr, 1, 9)
Entering recursiveMax(arr, 2, 9)
Entering recursiveMax(arr, 3, 9)
Entering recursiveMax(arr, 4, 9)
Entering recursiveMax(arr, 5, 9)
Entering recursiveMax(arr, 6, 9)
Entering recursiveMax(arr, 7, 9)
Entering recursiveMax(arr, 8, 9)
Entering recursiveMax(arr, 9, 9)
Leave recursiveMax(arr, 9, 9). Result = 10
Leave recursiveMax(arr, 8, 9). Result = 10
Leave recursiveMax(arr, 7, 9). Result = 10
Leave recursiveMax(arr, 6, 9). Result = 10
Leave recursiveMax(arr, 5, 9). Result = 10
Leave recursiveMax(arr, 4, 9). Result = 10
Leave recursiveMax(arr, 3, 9). Result = 40
Leave recursiveMax(arr, 2, 9). Result = 40
Leave recursiveMax(arr, 1, 9). Result = 40
Leave recursiveMax(arr, 0, 9). Result = 40
40

Perhaps it's just this example, but I have to add that this code is teaching you bad habits:
- recursiveMaximum()'s array parameter should be passed by const reference
- The last parameter should be one position past the end because that's the way everything in the standard library works.
- The function should return the index of the maximum item rather than the value, because that's much more useful.

[medosz]

Thank you for your help. It helped a lot.