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

#cpp #рекурсия

Не знаю как сделать поиск максимального элемента массива с помощью рекурсии. Есть идеи?

#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 << "\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;
}

    

Ответы

Ответ 1

Как и для других рекурсивных функций, достаточно реализовать простейший случай и
вызвать эту же функцию с меньшей задачей:

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)) << '\n';
}


Чтобы запустить:

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


Ответ 2

Можно, например, вот так:

#include 
#include 
#include 

int max(const std::vector::const_iterator& begin, std::vector::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 array{1, 55, 17, 77, 88, 13, 45, 72, 11};
    std::cout << max(array.сbegin(), array.сend(), std::numeric_limits::min())
<< "\n";
}


Есть массив,— вектор, в котором находится некоторый набор данных. Я в функцию max
передаю итераторы(можно считать указатели) на начало и конец(на одну позицию за концом)
массива. Базовым случаем рекурсии будет случай, когда элементы массива кончились, т.е.
начало и конец, переданные в аргументах, совпадают. В рекурсивном шаге мы проверяем,
является ли элемент, который находится в начала переданного промежутка большим, по
отношению к уже найденному максимальному, если да, то используем его, если нет, то
используем ранее найденный max.


Ответ 3

Вот еще вариант для массива (не вектора), с делением такового пополам (быстрее от
этого, конечно, он не работает :))

// Максимальный элемент в массиве 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]));
}


Ответ 4

Как рекурсию всегда можно представить итерацией, так и наоборот. 

В своем примере поиска максимума Вы используя итерацию перебираете все элементы массива,
соответственно простейшим будет вот такой естественный "однострочник" с рекурсией,
возвращающий максимум:

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


который на каждом следующем шаге рекурсии сдвигает начало массива на следующий элемент
и уменьшает количество элементов в нем на один.
Вызывать можно вот так:

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


Однако, в Вашем  примере несколько другая процедура, которая перебирает элементы
некоторого диапазона массива и возвращает индекс максимального в нем. Здесь по всем
шагам рекурсии нам надо вместе с текущим максимумом тащить еще и его индекс, который
в конце-концов и возвращается как результат.

Пожалуй, однострочник для нее выглядит несколько вычурно,  соответственно, рекурсивный
вариант, максимально похожий на Ваш пример, можно написать так:

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


и вот так использовать его для поиска максимального элемента во всем массиве

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


Довольно естественно, что если при поиске мы сначала полагаем, что начальный элемент
это максимум, то поиск проводим со следующего элемента. В самом деле,
зачем его сравнивать с самим собой?