Найти минимальное число в массиве с рекурсией?

int i = 0; int min = x[i]; while ( i < n ){ if ( x[i] < min ){ min = x[i]; } i++; } return min; 

Я написал итеративную форму, чтобы найти минимальное число массива. Но я хотел бы написать функцию с рекурсией. Пожалуйста помоги!

Поскольку это звучит как домашнее задание, вот подсказка: минимальное значение в массиве – это либо первый элемент, либо минимальное число в остальной части массива, в зависимости от того, что меньше.

Минимальное число одноэлементного массива – это один элемент в массиве.

Минимальное количество массива с размером> 1 является минимумом первого элемента и минимумом остальной части массива.

(Минимальное количество пустого массива не определено.)

Это не оптимальное решение, потому что вы можете сохранить результат рекурсивного вызова в переменной int, но мне не разрешили в этом упражнении.

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

Рекурсия останавливается на 0-индексе и затем сравнивает это значение с индексом 1. Затем он сравнивает наименьшее значение индекса 0 и 1 со значением из индекса 3 и так далее, пока не достигнет последнего значения.

 int minimum(int array[], int size) { if (size == 1) { return array[0]; } else { return (array[size] < minimum(array, size - 1)) ? array[size] : minimum(array, size - 1); } } int array[5] = {5, 99, 205, 1, 15}; int smallest = minimum(array, 4); // 4 = index of the last element 

Правила в моем упражнении:

  • Не меняйте массив
  • Не используйте переменную
  • Использовать рекурсию

Звучит как домашнее задание, но ваш лучший выбор – это примерно так:

 int main(void) { int size = 2; int test[] = {0,1}; int min = test[0]; findMin(&min, test, size); printf("%d", min); } void findMin(int* min, int* test, int* length); void findMin(int* min, int* test, int* length) { if (length >= 0) { if (*test < *min) { *min = test; } findMin(min, test++, (*length)--); } } 

Вот функция, которая вернет указатель на минимальное значение:

 #include  int *recursiveMin(int *x, int n) { if (x == NULL || n == 0) return NULL; if (n == 1) return x; int *t = recursiveMin(x + 1, n - 1); return *x < *t ? x : t; } 

общее правило рекурсии – избегать «малых шагов» – поэтому «первый элемент по сравнению с остальной частью массива» – очень плохая идея. попробуйте обработать массив пополам, например:

 min( array ) { if size of array == 1 return array[0] else if size of array == 2 return array[0] < array[1] ? array[0] : array[1] else { firstmin = min( firsthalf) // stored to avoid double calls secondmin = min( secondhalf) firstmin < second_min ? firstmin : secondmin } } 

для дальнейшей оптимизации:
- избегать копий массивов - рассмотрите возможность использования quicksort-подобной подписи (array, from, to)
- избежать рекурсивных вызовов для размеров <2

Почему вы хотите сделать это с помощью рекурсии? Общее правило с рекурсией не использует рекурсию, если вы можете сделать это в простой линейной петле.

Пытаться:

  int recursive_min(list arr) { return recursive_min(arr); } 

Хотя это не работает на императивных языках.

Более серьезным ответом было бы в псевдокоде:

 func recursive_min( list l ) { head = l[1] tail = l[2<->end] if l.length==1 return head else return min(head,recursive_min(tail)) } 

Хотя это не работает, если l пуст.

 int findMin(int a[], int len) { // normal version // if (len==1) return a[0]; // return (a[len-1] < findMin(a,len-1))? a[len-1] : findMin(a,len-1); // memoization version, sort of? int rightside; if (len==1) return a[0]; rightside = findMin(a,len-1); return (a[len-1] < rightside)? a[len-1] : rightside; } 
 #include  #include  using namespace std; int min(int [], int); void mostrar(int [], int); int main() { int f[] = {4, 9, 0, -1, 5, 8, -3, 6, -4, 0}; int t = sizeof(f)/sizeof(int); cout << "\nEl valor m\xa1nimo para los valores:\n"; mostrar(f, t); cout << "\nes: " << min(f, t); system("pause>nul"); } int min(int x[], int p) { if (p == 1) return x[0]; int aux = min(x+1, p-1); return x[0] < aux ? x[0] : aux; } void mostrar(int v[], int k) { if (k > 1) mostrar(v, k-1); cout << v[k-1] << " "; } 
 const int = 20; int getmin (int v[], int n); main () { int v[N]; int i,n,min; printf("\n\tType number of elements:\t"); scanf("%d",&n); for (i=0;i0) { if ( v[n-2] > v[n-1] ) { v[n-2]=v[n-1]; } getmin (v,n-1); } return v[n-2]; }