# 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, 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;
}
``````

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)
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;
}
``````
Scroll to Top