int i = 0;
int min = x[i];
while ( i < n ){
if ( x[i] < min ){
min = x[i];
}
i++;
}
return min;
I've written the iterative form to find the min number of an array. But I'd like to write a function that with recursion. Please help!
Because this sounds like homework, here's a hint: The minimum value in an array is either the first element, or the minimum number in the rest of the array, whichever is smaller.
The minimum number of a single-element array is the one element in the array.
The minimum number of an array with size > 1 is the minimum of the first element and the minimum of the rest of the array.
(The minimum number of an empty array is not defined.)
This is not an optimal solution, because you may save the result of the recursive call in an int variable, but I wasn't allowed to in my exercise.
Anyway, this function searches the lowest value in an int array by using recursion. As first it checks how many elements are in the array by checking if the size equals to 1 and then returns the first value as result. If the table is bigger than 1 (and technically also when lower) it compares the last value in the array with the recursive call with the rest of the array.
The recursion stops at the 0-index and then compares that value with the index 1. Then it compares the lowest value of index 0 and 1 with the value from index 3 and so on until it reaches 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
Rules in my exercise:
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)--);
}
}
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;
}
general rule of recursion is to avoid "small steps" - so "first element compared to rest of the array" is very bad idea. try to process the array in halves, like this:
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 array copies - consider using quicksort-like signature (array, from, to)
- avoid recursive calls for sizes < 2
Why do you want to do this with recursion? A general rule with recursion is don't use recursion if you can do it inside a simple linear loop.
min as the operation).Try:
int recursive_min(list<int> arr) {
return recursive_min(arr);
}
Although this doesn't 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 that doesn't work if l is empty.
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 <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] << " ";
}
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];
}
public int arrayMinValue(int[] array){
if(array.length == 1)
return array[0];
else
{
int valor = array[array.length-1];
int[] newArray = Arrays.copyOf(array, array.length-1);
Integer mun = arrayMinValue(newArray);
return mun <= valor? mun : valor;
}
}
This is a pseudo code
ALGORITHM Unknown (A[0,...,n-1] )
if n=1 then
return A[0]
else
temp<- Unknown (A[0,...,n-2] )
if temp<= A[n-1] then
return temp
else return A[n-1]
