Как найти максимальное число с помощью рекурсивной функции

Question

Я пытаюсь понять, как найти максимальное число, используя рекурсивную функцию, но я не совсем понимаю, как.Имея этот код:

#include <stdio.h>
#include <stdlib.h>
int main()
{

    int ar[100],n,i;
    int *ptr;
    printf("Enter size of the list:");
    scanf("%d", &n);
    printf("Printing the list:\n");
    for (i = 0; i < n ; i++)
    {
        scanf("%d", &ar[i]);
    }
    ptr=&ar;
    int max=maximum(ptr,n);
    printf("ma %d",max);
    return 0;
}
int maximum(int ar[], int n)
{

    int max;
    if(n+1==1)
    {
        return ar[n];
    }
    max =maximum(ar,n-1);
    return ar[n]>max?ar[n]:max;
}

Что он на самом деле делает и как?Правильно ли использовать указатели для указания массива целых чисел?Я надеюсь, что вы можете помочь мне понять это!

Answer 1

Учтите, что определение:

#include <stdio.h>
#include <stdlib.h>

void maximum(int nums[], int size, int index, int * max)
{
  if (index != size) {
    if (nums[index] > *max)
      *max = nums[index];
    maximum(nums, size, ++index, max);
  }
}

int main()
{
  int * nums;
  int size, i, max;

  fprintf(stderr, "Enter size of the list: "); /* stderr to flush without \n */
  if ((scanf("%d", &size) != 1) || (size <= 0)) {
    puts("wrong size");
    return 0;
  }

  if ((nums = malloc(size * sizeof(int))) == 0) {
    puts("cannot allocate nums");
    return 0;
  }

  for (i = 0; i != size; ++i) {
    if (scanf("%d", &nums[i]) != 1) {
      puts("invalid number");
      return 0;
    }
  }

  max = nums[0];
  maximum(nums, size, 1, &max);
  free(nums);
  printf("max = %d\n", max);

  return 0;
}

Исполнение:

% gcc -O2 -pedantic -Wall m.c
% ./a.out
Enter size of the list: 3
3
1
2
max = 3

максимум рекурсивно, но это рекурсия терминала ,поэтому компилятор может удалить его, чтобы сгенерировать цикл.Так что максимум кажется рекурсивным, когда вы запрашиваете, но стек не взорвется даже при большом числе:

% ( echo 100000000 ; yes 1 ) | ./a.out
Enter size of the list: max = 1

Если я уберу опцию -O2, генерирующий код использует рекурсиюи стек взрывается:

% gcc -pedantic -Wall m.c
% ( echo 100000000 ; yes 1 ) | ./a.out
Enter size of the list: Segmentation fault

Answer 2

Вы выделяете память для массива из 100 целых чисел с помощью int ar[100] и вводите n, который устанавливается с помощью scanf("%d", &n).Если на этом этапе вы введете число больше 100, ваша программа будет вызывать ошибку, потому что ваш цикл for (i = 0; i < n ; i++) попытается получить доступ к ar[100], что является ошибкой доступа к памяти (самый высокий доступный индекс массива равен ar[100 - 1], обратите внимание, что 100- 1 <100).В любом случае, вы заполняете <code>n индексы ar в цикле.ptr = &ar просто назначает начальный адрес ar для ptr.Кстати ptr = ar тоже будет работать, & не нужен.Теперь вы можете использовать ptr так же, как вы использовали ar.

Самый простой способ понять рекурсию - это перейти прямо к последнему вызову maximum.Но сначала, поймите, что вы передали ptr в функцию, которая аналогична передаче ar (помните, они одинаковы в main с ptr = ar.).

Так что впоследний вызов maximum, когда n + 1 == 1 (аналогично n == 0), возвращается ar[n], равный ar[0], который является первым номером, который вы ввели для 'Printing the list' (он был сохранен в ar[0]).

Теперь во втором последнем вызове maximum, n + 1 == 1 ложно, потому что n = 1, поэтому мы переходим к max = maximum(ar, n - 1).Это результат последнего вызова maximum, который я только что объяснил, поэтому max имеет значение ar[0].Теперь у вас есть return ar[n] > max ? ar[n] : max, что совпадает с return ar[1] > ar[0] ? ar[1] : ar[0].Это то же самое, что

if (ar[1] > ar[0]) {
  return ar[1];
} else {
  return ar[0];
}

И вы можете видеть, что это возвращается в зависимости от того, что больше: ar[0] или ar[1].Теперь для третьего последнего вызова maximum, max является результатом второго последнего вызова maximum.И вы можете видеть, как картина появляется.Вы вернете в зависимости от того, что больше: max или ar[n] для всех остальных вызовов на maximum, и к тому времени, как вы получите первый вызов maximum, вы сравните все значения в ar чтобы найти его максимум и вернуть его.

Также, как сказал Аджай, правильно, ar[n] обращается к значению, которое вы никогда не инициализировали в цикле.Вы должны написать int max = maximum(ptr, n - 1) в main, чтобы исправить это.

Answer 3

Мое решение с хвостовой рекурсией:

int maximum(int a[], int n)
{
    if (n == 1)
        return a[0];
    --n;
    return maximum(a + (a[0] < a[n]), n);
}

Демонстрация в проводнике компилятора

Answer 4

Чтобы понять, как работает maximum, просто попробуйте найти некоторые инварианты в функции maximum

int maximum(int ar[], int n)
{
    int max;
    if(n==0)
    {
        return ar[n];
    }
    max =maximum(ar,n-1);
    /* at this point MAX keeps the maximum of the subarray [0..N-1] and using this 
       we try to get by induction the maximum of [1..N]. */
    return ar[n]>max?ar[n]:max;
}