Like Tree1Likes
  • 1 Post By grumpy

Find minimum in an array, using recurssion.

This is a discussion on Find minimum in an array, using recurssion. within the C Programming forums, part of the General Programming Boards category; This seemingly right code, don't know why gives 0 always as output. Please, help debugging it... Code: #include <stdio.h> int ...

  1. #1
    Registered User
    Join Date
    Feb 2011
    Posts
    52

    Find minimum in an array, using recurssion.

    This seemingly right code, don't know why gives 0 always as output. Please, help debugging it...

    Code:
    #include <stdio.h>
    
    int min(int *arr,int size)
    {
    	static int *m;
    
    	if(!m) m=arr;
    
    	return size ? ( *m>*++arr ? min((m=arr),size-1) : min(arr,size-1) ) : *m;
    }
    
    int main(void)
    {
    	int i,size;
    
    	printf("Enter array size:");
    	scanf("%d",&size);
    
    	int arr[size];
    
    	printf("Enter array elements:");
    	for(i=0;i<size;i++)
    	scanf("%d", arr+i);
    
    	printf("The minimum no. is %d",min(arr,size));
    
    	return 0;
    }

  2. #2
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,762
    >> min((m=arr),size-1)

    The result of an assignment expression is the left hand side. Are you sure you want to pass in m and not arr?

    Also I wouldn't use a static variable at all. It's just far too much trouble -- min can only really be used with one array because they can only be initialized once and your code to assign to m is no help.

  3. #3
    Registered User
    Join Date
    Feb 2011
    Posts
    52
    Yeah, because its equivalent whether I pass m or arr, its essentially the same address.
    And I thought if i dont use m, where do i store the the minimum value of the array????
    Last edited by Avenger625; 02-11-2012 at 01:11 AM.

  4. #4
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,762
    Yeah, because its equivalent whether I pass m or arr, its essentially the same address.
    It may be the same address, but the variables clearly don't mean the same. m is supposed to point at the minimum element. You start using m to iterate through the array and the result for m will always be something the same, since you have to go through the whole array to even find the minimum.

    And I thought if i dont use m, where do i store the the minimum value in the array????
    It's not storage that is the real problem, it's just that static variables of any type are very inflexible. A static variable can only be initialized once.

    >> if(!m) m = arr;
    This will only be true once, in fact, it's only true the first time it's tested. You can't ever use min on a different array.

  5. #5
    Registered User
    Join Date
    Feb 2011
    Posts
    52
    May be there is a bit of misunderstanding...let me tell how I thought then may b it will be easier for you to help me.
    1. Initialize a static variable that will hold/point to the min. value of the array(till the index traversed), between the recursive function calls.
    2. The array is being passed to min(); so for first time and only once initialize m with the value at the first index of the array.
    OR for first time and only once let m point to the value at the first index of the array. [m=arr]
    3. arr is incremented, so essentially arr points to arr[1]; now the comparison is done
    a. if its smaller than arr[0] m will point to it - the min value in the array till the index traversed (in this case 1).
    b. if not it will point to arr[0] - - the min value in the array till the index traversed (in this case 1).
    4. Function min is called with
    a. arr (index already checked is cropped, here 0 checked with 1 so 0 cropped out), cropping them out because we don't need them as well.
    b. size-1, to check we don't overrun the array.*
    5. This recursion continues till size is 0 and finnaly returns the value at m.


    So essentially and logically, at least in this prog., min((m=arr),size-1) is same.


    * I could not think of any way...and basically i dont think there is a way to check we did not overran the array without size, just by using arr. Please share if you know one.
    Last edited by Avenger625; 02-11-2012 at 01:47 AM.

  6. #6
    Registered User
    Join Date
    Sep 2011
    Posts
    111
    The trick with recursion is breaking the problem to the first step and letting the function do the rest.

    Define the base case, in this case maybe once you reach the end or the array.

    Solve for the very first case, as in testing array element 0.

    Maybe something like this...


    Code:
    int min(int *arr,int size) //might want to consider in passing in three args (int *arr, int size, int accumulator)
    {
       //Accumulator (acc)
       //set the acc equal to the first element of the array
       //if at the array end(assuming size in your case) return the acc.
      
      //call the function again, comparing the acc to the next element of the array.
    }

  7. #7
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,762
    (shrug)
    I screwed most of this up. I still wouldn't use a static variable though.

    1. Initialize a static variable that will hold/point to the min. value of the array(till the index traversed), between the recursive function calls.
    A third argument would work just as well.

    2. The array is being passed to min(); so for first time and only once initialize m with the value at the first index of the array.
    2. The array is being passed to min, if this is the first time min() has ever been called this run of the program, initialize m to NULL.

    if (!m) m = arr;

    And m is never NULL again because of static stickyness, even if you wanted it to be. Meaning that no other array could ever be used by min in the same run of the program.

    Now to cover the rest of the issues:
    Code:
    Microsoft Windows XP [Version 5.1.2600]
    (C) Copyright 1985-2001 Microsoft Corp.
    
    C:\Documents and Settings\User>notepad a.c
    
    C:\Documents and Settings\User>gcc a.c -std=c99
    
    C:\Documents and Settings\User>a
    Enter array size:
    3
    Enter array elements:
    1
    2
    3
    The minimum no. is 1
    C:\Documents and Settings\User>a
    Enter array size:3
    Enter array elements:2
    1
    3
    The minimum no. is 1
    I should have tried it earlier. I can't reproduce your problem. Did you forget to do something I haven't? Like, are you sure you're using C99...
    Last edited by whiteflags; 02-11-2012 at 02:33 AM.

  8. #8
    Registered User
    Join Date
    Jun 2005
    Posts
    6,646
    That min() should never be called with size zero. It eventually will be.

    It would be much easier to implement a recursive min() function without a static.
    stahta01 likes this.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Sunshine, and read this, this, and this before posting again.

  9. #9
    Registered User
    Join Date
    Feb 2011
    Posts
    52
    @grumpy:
    That min() should never be called with size zero. It eventually will be.
    Sorry I could not actually catch what or why is it for?! Could you please take the trouble of explaining it to me again.

    @whiteflags: The program was run on -
    1. Pelles C x64 on Windows 7 Ultimate SP1 (64 bit) - it always gave the same error for different sets of inputs, It always prints, The minimum no. is 0
    2. Dev-CPP (32 bit) on same platform - it gave correct answers for all different sets of input.

    I cant find any logical or technical errors in my code. So what's actually going wrong.....???????????

    @all: thanks and would appreciate further help on this....if any one has a definite reason for this nonsense....

  10. #10
    Registered User
    Join Date
    Jun 2005
    Posts
    6,646
    You need to look at all the potential cases for which min() might be called with size zero. You will find that at least one of those cases results in an out-of-bound access. The fact you are using a static just muddies the water and makes such cases harder to recognise.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Sunshine, and read this, this, and this before posting again.

  11. #11
    Registered User
    Join Date
    Sep 2011
    Posts
    111
    Quote Originally Posted by Avenger625 View Post
    1. Pelles C x64 on Windows 7 Ultimate SP1 (64 bit) - it always gave the same error for different sets of inputs, It always prints, The minimum no. is 0
    2. Dev-CPP (32 bit) on same platform - it gave correct answers for all different sets of input.
    This is just a guess, but it might be how things are being computed via 64/32 bit.

    One option you can try is, using the Debug mode of Pelles (assuming it has one) and step through your code line by line. And see how values are changing and what they are changing to.

  12. #12
    Registered User
    Join Date
    Feb 2011
    Posts
    52
    @grumpy: I see. Thanks. It works fine now when min() is not called with size 0. But my question is - Why did Dev-Cpp work fine with that but not Pelles C x64?????

  13. #13
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,271
    Quote Originally Posted by Avenger625
    It works fine now when min() is not called with size 0. But my question is - Why did Dev-Cpp work fine with that but not Pelles C x64?????
    An out of bounds access results in undefined behaviour, so it could well work when compiled with Pelles C too, on weekends
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Recurssion issues.
    By mrkrinkle in forum C Programming
    Replies: 1
    Last Post: 03-20-2011, 05:22 PM
  2. find more than one minimum
    By saudi-vip in forum C Programming
    Replies: 3
    Last Post: 11-14-2008, 02:57 AM
  3. Finding the minimum value in an array?
    By kabuatama in forum C Programming
    Replies: 8
    Last Post: 02-18-2006, 01:45 PM
  4. finding non-zero minimum in array
    By xstudent in forum C Programming
    Replies: 8
    Last Post: 12-16-2002, 03:58 AM
  5. finding minimum in array
    By xstudent in forum C# Programming
    Replies: 3
    Last Post: 12-15-2002, 12:23 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21