Найти максимум одномерного массива c помощью рекурсии C++

Не знаю как сделать поиск максимального элемента массива с помощью рекурсии. Есть идеи?
#include
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 << "
введи a[" << i << "] "; cin >> a[i]; } for(i = 1; i <= n; i++) { cout << " a[" << i << "]=" << a[i]; } cout << "
"; 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; }

Ответ

Как и для других рекурсивных функций, достаточно реализовать простейший случай и вызвать эту же функцию с меньшей задачей:
template 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 }
если слово template не ясно, то чтобы не отвлекаться (это не важно для понимания рекурсии), можно просто заменить ForwardIt на float*
Простейшим случаем здесь является пустой массив (first == last), в этом случае функция просто возвращает largest аргумент.
Чтобы уменьшить размер задачи, можно отбросить первый элемент first—обновив largest, если необходимо—и вызвать функцию рекурсивно c остатками ввода, чтобы завершить решение задачи.
Для удобства использования, можно определить функцию с двумя параметрами, передавfirst в качестве начального значения для largest—это работает и для пустых массивов, в этом случае возвращается значение равное last
template ForwardIt max_element(ForwardIt first, ForwardIt last) { return max_element(first, last, first); }
Пример использования:
#include
int main() { float a[] = {1, -2, 3, 0.5}; std::cout << *max_element(a, a + sizeof(a) / sizeof(*a)) << '
'; }
Чтобы запустить:
$ g++ max_recursive.cc && ./a.out 3

В данном случае max_element() является так называемой tail-recursive функцией—рекурсивный вызов является хвостовым (последним) в функции и может не потреблять стек. Некоторые компиляторы умеют автоматически преобразовывать подобный код в циклы, например, gcc -O2 для ForwardIt=int* может сгенерировать вот такой ассемблер
# 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
Абсолютно такой же код получается из итеративной версии
int* max_element(int* first, int* last, int* largest) { for ( ; first != last; ++first) if (*largest < *first) largest = first;
return largest; }