I have to write a C code that finds the smallest value in an array using recursion. I've already done it using the for loop, but recursion is trickier . Can someone help me??
11
-
8what you tried so far?Jayesh Bhoi– Jayesh Bhoi2014-08-20 12:23:34 +00:00Commented Aug 20, 2014 at 12:23
-
3Have you tried anything yet ? Go as always with recursion : solve the degenerate case (one-element array) then work up the general case.Quentin– Quentin2014-08-20 12:23:45 +00:00Commented Aug 20, 2014 at 12:23
-
1For large arrays, you could (conceptually) split them in half and consider each half. Here is the recursion!Basile Starynkevitch– Basile Starynkevitch2014-08-20 12:24:51 +00:00Commented Aug 20, 2014 at 12:24
-
the user has asked the first question here, and get a down vote!! @angie please post what you've tried and welcom on SOEngine– Engine2014-08-20 12:25:47 +00:00Commented Aug 20, 2014 at 12:25
-
2@angie I suggest you that don't see the answers. Please find your solution by a simple example like an array with 1 element, then with 2 elements, then 3 elements, and so on. You may find your answer after three steps.Nematollah Zarmehi– Nematollah Zarmehi2014-08-20 12:36:53 +00:00Commented Aug 20, 2014 at 12:36
|
Show 6 more comments
5 Answers
The minimum of a single item array is that single item (base case or the termination condition).
The min of an array is the minimum of [the first item, the minimum from the rest (excluding the first item)]
Comments
Here is simple code for finding minimum value using recursion,
int rec(int a[],int n)
{
int min;
if(n==1)
return a[0];
else {
min=rec(a,n-1);
if(min<a[n-1])
return min;
else
return a[n-1];
}
}
void main()
{
int i,j,n,a[20];
printf("enter n :");
scanf("%d",&n);
printf("enter values : ");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
printf("\n%d",rec(a,n));
getch();
}
5 Comments
Martin James
Congrats - you put more effort into providing a read-made copy-paste straight-to-homework answer than the OP did in writing the question and searching for solutions.
angie
it's not like that, i need to undertsand that answer, not just copy-paste it
David Ranieri
void main is a pain.angie
I don't understand this: min=rec(a,n-1); I know that a[] is the array, but i still don't get it.
PU.
For this you need to understand execution of recursive function via program stack .. this link may help mooreccac.com/kcppdoc/Recursion.htm
#include <stdio.h>
int minimum(int *a_s, int *a_e, int candidate){
if(a_s == a_e)
return candidate;
return minimum(a_s+1, a_e, *a_s < candidate ? *a_s : candidate);
}
int main(void){
int array[] = { 1,3,-2,0,-1};
printf("%d ", minimum(array+1, &array[sizeof(array)/sizeof(*array)], *array));
return 0;
}
2 Comments
Quentin
It's probably not a good idea to do OP's homework. Plus, your code would probably be cryptic to a beginner.
chux
@Quentin We do not know this is homework nor from a beginner (wink, wink, ;-)). Still, providing an answer that needs work to understand on OP's part looks like a good idea to me in response to such a post.
After accept answer.
Below is a recursive solution that does not chew up the stack. Estimate max stack depth at O(ln2(n)). Other solutions look like the maximum stack depth is O(n).
int ArrayMin(const int a[], size_t n) {
if (n <= 1) {
if (n < 0) return 0; // Handle degenerate ArrayMin( ,0)
return a[0];
}
size_t nhalf = n / 2;
int left = ArrayMin(a, nhalf);
int right = ArrayMin(&a[nhalf], n - nhalf);
return left < right ? left : right;
}
Answered after 9 hours, we can assume homework due date is past.
Comments
- Consider first element of the array is minimum.
- Call the function by passing base address of the array and number of elements.
- Check for any other number is less then the minimum value, if yes assign that value to minimum.
- For every iteration increment the array address and decrement the no of elements!
Try this code-
#include<stdio.h>
int min;
int arrfun(int *arr,int n)
{
if(n){
if(*arr < min) // check any no is less than minimum.
min = *arr; // if yes assign it
}
else
return min; // when n becomes 0 it returns the minimum element
arrfun(++arr,--n); // recursive call
}
int main()
{
int arr[]={7,3,9,2,1,6};
min = arr[0]; // Taking first element is minimum
printf("minimum is: %d\n",arrfun(arr,6)); // call the function by passing address and no of elements in array
return 0;
}
1 Comment
mch
you forgot a
return at the end of arrfun. Also I have never seen a recursion using a global variable.