Нужна помощь в понимании этой рекурсивной функции - PullRequest
Новая
       11

Нужна помощь в понимании этой рекурсивной функции

1 голос
/ 23 марта 2020

Я изучаю рекурсию, и мы должны получить наибольшее число из массива, но я не понимаю решения. 

#include<stdio.h>
#include<stdlib.h>
int biggestNumber(int *array, int n);

int main(void){
  int n=3;
  int array[3]={3,4,1};
  fprintf(stdout, "|||||%d\n", biggestNumber(array,n));
  return 0;
}

int biggestNumber(int *array, int n){
  if(n==1){
    return array[0];
  }
  else{
    if(array[n-1]>biggestNumber(array, n-1)){
      return array[n-1];
    }
    else{
      return biggestNumber(array, n-1);  
    }
  }
}

Кажется, я не могу понять эту рекурсивную функцию. После того, как array[n-1]>biggestNumber(array, n-1) ложно, я не понимаю возврат к той же функции.

1 Ответ

0 голосов
/ 23 марта 2020

Для начала определение рекурсивной функции неверно и, как правило, может привести к неопределенному поведению.

Первый параметр должен быть объявлен с квалификатором const, поскольку массив не изменяется в функции.

Второй параметр должен иметь тип size_t.

Внутри функции рекурсивные вызовы могут вызываться два раза, если, например, первый оператор if выдает false. 

if(array[n-1]>biggestNumber(array, n-1)){
              ^^^^^^^^^^^^^^^^^^^^^^^^^
  return array[n-1];
}
else{
  return biggestNumber(array, n-1);  
         ^^^^^^^^^^^^^^^^^^^^^^^^^
}

Функция может быть объявлена ​​и определена так, как показано в демонстрационной программе. ниже 

#include <stdio.h>

size_t biggestNumber( const int a[], size_t n )
{

    if ( n < 2 )
    {
        return 0;
    }
    else
    {
        size_t max_i = biggestNumber( a, n - 1 );
        return a[max_i] < a[n-1] ? n - 1 : max_i;
    }
}

int main(void) 
{
    int a[] = { 3, 4, 1 };
    const size_t N = sizeof( a ) / sizeof( *a );

    size_t i = biggestNumber( a, N );

    printf( "The biggest number is %d\n", a[i] );

    return 0;
}

Вывод программы: 

The biggest number is 4

Принцип прост. Поскольку функция является рекурсивной, то для любого заданного n (количество элементов в массиве) функция находит индекс максимального элемента в массиве с первыми n -1 элементами. А затем сравните найденный максимум в подмассиве с элементом с индексом n-1.

Например, для первого рекурсивного вызова функция ищет индекс максимального элемента в подмассиве { 3, 4 }.

Для этого подмассива функция вызывает себя для подмассива, состоящего из одного элемента {3}. Это значение является максимальным значением подмассива, поскольку массив солнца содержит только один элемент. Таким образом, индекс элемента, который равен 0, возвращается к предыдущему вызову функции.

Теперь функция сравнивает значения возвращаемого максимума, равного 3, с элементом с индексом (n - 1), т.е. с индексом 1, равным 4. Таким образом, функция возвращает индекс 1 первому вызов функции.

Здесь снова проводится сравнение максимума, равного 4, со значением элемента по индексу (n - 1), которое в этом вызове равно 2. В качестве значения 1 меньше значения 4, то возвращается индекс 1, индекс максимального значения.

...