Find the minimum number in an array with recursion?

Question

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

I wrote an iterative form to find the minimum number of array. But I would like to write a function with recursion. Please, help!

Answer 1

Since this sounds like homework, here's a tip: the minimum value in the array is either the first element or the minimum number in the rest of the array, whichever is less.

Answer 2

The minimum number of a singleton array is one element in the array.

The minimum number of an array with a size> 1 is the minimum of the first element and the minimum of the rest of the array.

(The minimum number of empty arrays is undefined.)

Answer 3

This is not an optimal solution, because you can save the result of a recursive call in an int variable, but I was not allowed in my exercise.

In any case, this function searches for the smallest value in the int array using recursion. How first he checks how many elements are in the array, checking if size is 1, and then returns the first value as a result. If the table is greater than 1 (and technically also lower), it compares the last value in the array with a recursive call with the rest of the array.

The recursion stops at the 0-index, and then compares this value with index 1. Then it compares the smallest value of index 0 and 1 with the value from index 3, and so on, until it reaches the last value.

 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 

The rules in my exercise:

• Do not change the array
• Do not use variable
• Use recursion

Answer 4

Sounds like homework, but your best bet is something like this:

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

Answer 5

Here is a function that will return a pointer to the minimum value:

 #include <stddef.h> 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; } 

Answer 6

A general recursion rule is to avoid "small steps" - therefore, "the first element compared to the rest of the array" is a very bad idea. try processing the array in half, for example:

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

for further optimization:
- avoid copies of arrays - consider using a quicksort-like signature (array, from, to)
- avoid recursive calls for sizes <2

Answer 7

Why do you want to do this with recursion? The general rule with recursion does not use recursion if you can do this in a simple linear loop.

Answer 8

Try:

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

Although this does not work in imperative languages.

A more serious answer would be in pseudocode:

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

Although this does not work if l is empty.

Answer 9

 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;i<n;i++) { printf("\nv[%d]:\t",i); scanf("%d",&v[i]); } min = getmin (v,n); printf("\n\n\tMinimume value is %d.",min); } int getmin (int v[],int n) { if (n>0) { if ( v[n-2] > v[n-1] ) { v[n-2]=v[n-1]; } getmin (v,n-1); } return v[n-2]; } 

Answer 10

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

Answer 11

 #include <iostream> #include <cstdlib> 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] << " "; }