Есть ли способ найти ИНДЕКС минимального значения в массиве с помощью рекурсивной функции? C ++

Question

Мне нужно найти индекс минимального числа в массиве, используя рекурсивную функцию в c ++, функция может получить только 2 параметра: указатель на массив и его размер.

int smallest(int arr[], int num);

Мне удалось это сделать, но с помощью вспомогательной переменной, которая является stati c и объявлена ​​вне функции, вот что я получил:

static int flag = 0;
int smallest(int* arr, int num) {
   if (flag == num - 1)
      return flag;
   if (arr[num - 1] > arr[flag]) {
      return smallest(arr, num - 1);
   } else {
      flag++;
      return smallest(arr, num);
   }
}

Теперь мой вопрос может Я делаю это без переменной stati c или любой другой переменной, кроме num? вот что я получил до сих пор:

int smallest(int arr[], int num) {
    if (arr != &arr[num - 1])
        if (*arr < arr[num - 1])
            smallest(arr, num - 1);
        else
            smallest(arr + 1, num);
    return num - 1;
}

Он не возвращает индекс минимального значения, но доходит до своего адреса, функция завершается, когда адрес указателя массива совпадает с адресом минимального значения. Как я могу получить его, чтобы вернуть индекс?

Я студент, и я довольно плохо знаком с C ++, я ценю помощь! спасибо!

===

edit:

это изначально домашнее задание, но ограничение не использовать внешние справочные переменные или функции - мое! и мне любопытно узнать, возможно ли это вообще.

Answer 1

Поскольку это, очевидно, домашнее задание, я не собираюсь раскрывать ФАКТИЧЕСКИЙ ответ в полном объеме, но дам несколько (надеюсь) полезных советов.

При рекурсии сначала подумайте, каково ваше конечное состояние является. Это должен быть массив из 1 элемента. В этом случае вы возвращаете индекс 0 из-за имеющегося у вас массива, это единственный элемент, поэтому возвращайте его индекс.

if(num == 1)
{
    return 0;
}

Так чем же это полезно для вас? Сравните это ровно с одним другим элементом. Вот как ты сломаешь это. Ваш массив превращается в «один элемент и много» или «это всего лишь один элемент». Если это только один, вернуть единственное значение. Если их много, назовите себя рекурсивно со второго элемента (индекс 1) и далее:

int restOfArraySmallest = smallest(arr+1, num-1) + 1;

Вам нужен +1, потому что вы смещены относительно того, откуда он начинается. Но вы знаете, что значение в restOfArraySmallest является индексом в ВАШИХ arr наименьшего значения из всех , за исключением первого элемента. Поскольку ваши рекурсивные вызовы не включают в себя первый элемент, только остальные.

Надеюсь, этого достаточно, чтобы вы получили остальную часть пути.

Редактировать: потому что ОП ответил и сказал это не было существенным для их домашнего задания, вот вся функция:

// Recursively finds the index of the smallest element of the passed-in array
int smallest(int* arr, int num)
{
    if(num <= 1)
    {
        return 0;  // If we're in the last element, the smallest is the only element
    }
    // More than one element, so find the least element in all the elements
    // past the first element of the array
    // Note: the index returned is offset from our current view of the array,
    //       so add +1 to any returned result so we can index directly from it
    int restOfArraySmallest = smallest(arr+1, num-1) + 1;

    // Compare the first element in the array to the smallest of the entire rest
    // of the array:
    if(arr[0] < arr[restOfArraySmallest])
    {
        // The first element is smaller, it's the smallest, so return that index
        return 0;
    }
    else
    {
        // The element already found is smaller, so return that index.  It's already
        // correctly offset
        return restOfArraySmallest;
    }
}

И это все. Если есть дубликаты записей для самых маленьких, предпочтение будет отдаваться последним.

Хитрость с рекурсией состоит в том, чтобы НЕ сохранять внешние переменные. То, что вы передаете в качестве аргументов и RETURN BACK, - это вся информация, которая у вас есть. Для некоторых алгоритмов этого достаточно.

Обратите внимание: если вы используете рекурсивные функции с достаточно большими наборами данных, вы в конечном итоге получите переполнение стека. Не сайт, тип cra sh. Этот алгоритм довольно легок в том, что только одна дополнительная переменная и два аргумента сами распределяются при каждом проходе, но в итоге он складывается.