I do not know how to make the search for 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; }
  • one
    why such strange homework is given, is it really impossible to come up with a task where the recursion is somehow meaningful :( - splash58
  • I do not understand. What a day I think about it. - Sergo E
  • @ splash58 For example, for such a container as std::map recursive search for a minimum / maximum is very convenient. What is your data storage structure? And give at least an attempt to implement the search. - StateItPrimitive
  • one
    @SergoE click "edit" and put code in question - splash58
  • one
    @SergoE, you need to edit not a comment, but a question. It is not necessary to place the code in the comments - ixSci

4 answers 4

As for other recursive functions, it suffices to implement the simplest case and call the same function with a smaller 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 task, you can drop the first element first updating the largest if necessary — and call the function recursively with the input residuals to complete the task.

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

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

Example of use:

 #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) in the function and may not consume the stack. Some compilers can automatically convert such code into loops, for example, gcc -O2 for ForwardIt=int* can generate such an 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

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

    You can, for example, like this:

     #include <iostream> #include <vector> #include <limits> int max(const std::vector<int>::const_iterator& begin, std::vector<int>::const_iterator& end, int curentMax) { if(begin == end) return curentMax; if(*begin > curentMax) return max(begin + 1, end, *begin); return max(begin + 1, end, curentMax); } int main() { std::vector<int> array{1, 55, 17, 77, 88, 13, 45, 72, 11}; std::cout << max(array.сbegin(), array.сend(), std::numeric_limits<int>::min()) << "\n"; }

    There is an array, - a vector in which there is a certain data set. I pass iterators to the max function (pointers can be read) to the beginning and end (one position after the end) of the array. The basic case of recursion will be the case when the array elements have run out, i.e. The beginning and end passed in the arguments are the same. In the recursive step, we check whether the element that is at the beginning of the transmitted interval is large with respect to the maximum already found, if so, use it, if not, then use the previously found max .

    • I unfortunately do not have such a set of knowledge to understand your code. - Sergo E
    • @SergoE, but what's not clear? - ixSci
    • My knowledge is less than you expect. I have to use using namespace std and recursion to set using an ordinary function, and so return can only be used once. - Sergo E
    • @SergoE, I can write a full version for you that you can go and pass, but who is studying here, or you, will it make sense that you will not understand anything? In a recursive function there will always be at least 2 returns, one for the base case, the other for the recursive. You can, of course, use the output link instead of the return value, but this is, firstly, more complicated, and secondly, crooked. - ixSci
    • one
      Well, I find fault with the words. you will break the boy's life - he will tell the teacher that way. - splash58

    Here's another option for an array (not a vector), with the division of such in half (faster from this, of course, it does not work :))

     // Максимальный элемент в массиве array с индексами [start,stop) int maxel(int * array, int start, int stop) { if (start == stop-1) return array[start]; int mid = (start + stop)/2; int m1 = maxel(array,start,mid), m2 = maxel(array,mid,stop); return (m1 > m2) ? m1 : m2; } int main(int argc, const char * argv[]) { int x[] = { 1,2,15,2,41,18,-4,2 }; cout << maxel(x,0,sizeof(x)/sizeof(x[0])); }
    • maybe it works, because the recursion depth of log (N) and not N ==> is less overhead, and flying out of the stack is also not threatened. - pavel
    • @pavel Well, except in this sense. I meant, that all the same O (N). - Harry
    • on the middle element - three function calls :) - splash58
    • @pavel: the disadvantage of this version is that it doesn’t seem to work ( most programmers make mistakes when implementing a binary search , which the code in the response looks like without a reason), and the recursive call is not tail, so the compiler cannot convert it into a loop. Both in my answer and in the @ixSci answer, tail recursive calls are used, so optimization is possible. - jfs

    As recursion can always be represented by iteration, so and vice versa.

    In your example of finding the maximum, using iteration, you iterate through all the elements of the array, respectively, the simplest one would be such a natural one-liner with recursion, which returns the maximum:

     float rfmax (float *a, int n, float cmax) { return n > 0 ? rfmax(a + 1, --n, cmax > *a ? cmax : *a) : cmax; }

    which at each subsequent recursion step shifts the beginning of the array to the next element and reduces the number of elements in it by one.
    You can call like this:

     int n = ... float a[n]; ... printf("max: %f\n", rfmax(a + 1, n - 1, a[0]));

    However, in your example, there is a slightly different procedure that iterates over the elements of a certain array range and returns the maximum index in it. Here, along all the steps of recursion, we have to drag along with the current maximum its index, which eventually returns as a result.

    Perhaps, the one-liner for her looks a bit pretentious, respectively, a recursive version, most similar to your example, can be written like this:

     int ixfmax (float a[], int start, int end, float cmax, int icmax) { if (start > end) return icmax; if (cmax < a[start]) cmax = a[icmax = start]; return ixfmax(a, start + 1, end, cmax, icmax); }

    and so use it to find the maximum element in the entire array

      int imax = ixfmax(a, 1, n - 1, a[0], 0); printf("max: a[%d] = %f\n", imax, a[imax]);

    It is quite natural that if, in a search, we first assume that the initial element is a maximum, then we search from the next element. In fact, why compare it with yourself?