c++ – Find the maximum of a one-dimensional array using C ++ recursion

Question:

I don’t know how to find the maximum element of an array using recursion. Any ideas?

#include <iostream> 

using namespace std;
const int n = 5;
float a[n + 1];
int fmax(float a[], int nach, int kon); 

int main() {
    int i, k; for(i = 1; i <= n; i++) {
        cout << "\n введи a[" << i << "] ";
        cin >> a[i];
    } for(i = 1; i <= n; i++) {
        cout << " a[" << i << "]=" << a[i];
    }
    cout << "\n";
    cout << fmax(a[5], 0, 4); return(0);
}
int fmax(float a[], int nach, int kon)
{
    int k, kmax;
    float max; 
    kmax = nach;
    max = a[nach]; 
    for(k = nach; k <= kon; k++)
    {
        if(a[k] > max)
        {
            max = a[k]; kmax = k;
        }
    } 
    return kmax;
}

Answer:

As with other recursive functions, it is enough to implement the simplest case and call the same function with less task:

template<class ForwardIt>
ForwardIt max_element(ForwardIt first, ForwardIt last, ForwardIt largest)
{
  if (first == last)  // no more elements to compare
    return largest;

  if (*largest < *first) // compare with the first element
    largest = first;

  ++first;
  return max_element(first, last, largest); // compare the rest
}

^{if the word template not clear, then in order not to be distracted (this is not important for understanding recursion), you can simply replace ForwardIt with float* .}

The simplest case here is an empty array ( first == last ), in which case the function simply returns the largest argument.

To reduce the size of the problem, you can discard the first element first updating largest if necessary — and call the function recursively with the remainder of the input to complete the problem.

For ease of use, you can define a function with two parameters, passing first as the initial value for largest — this works for empty arrays as well, in which case last is returned:

template<class ForwardIt>
ForwardIt max_element(ForwardIt first, ForwardIt last)
{
  return max_element(first, last, first);
}

Usage example:

#include <iostream>

int main()
{
  float a[] = {1, -2, 3, 0.5};
  std::cout << *max_element(a, a + sizeof(a) / sizeof(*a)) << '\n';
}

To start it:

$ g++ max_recursive.cc && ./a.out
3

---

In this case, max_element() is the so-called tail-recursive function — the recursive call is the tail (last) call in the function and may not consume the stack. Some compilers are able to automatically convert such code into loops, for example, gcc -O2 for ForwardIt=int* can generate the following assembler :

                                    #   first  : %rdi
                                    #   last   : %rsi
                                    #   largest: %rdx
                                    #   result : %rax

max_element(int*, int*, int*):
        cmpq    %rsi, %rdi          # x = cmp(first, last)
        movq    %rdx, %rax          # result = largest
        je      .L2                 # if(first == last) return result // if(!x)
.L4:                                # do {
        movl    (%rdi), %ecx        # y = *first
        cmpl    %ecx, (%rax)        # z = cmp(*result, y)
        cmovl   %rdi, %rax          # if (*result < y) result = first //if(z<0)
        addq    $4, %rdi            # ++first
        cmpq    %rdi, %rsi          # x = cmp(last, first)
        jne     .L4                 # } while (last != first) // while(x)
.L2:
        rep ret                     # return result // rep is amd
                                                    // brancher bug workaround

Exactly the same code is obtained from the iterative version :

int* max_element(int* first, int* last, int* largest)
{
  for ( ; first != last; ++first) 
    if (*largest < *first) 
      largest = first;  

  return largest;
}