find largest in array with recrusion

This is a discussion on find largest in array with recrusion within the C Programming forums, part of the General Programming Boards category; Wrote this one to find largest integer in one dimensional array. It has to be done without global or local ...

  1. #1
    Registered User
    Join Date
    Jun 2004
    Posts
    123

    find largest in array with recrusion

    Wrote this one to find largest integer in one dimensional array. It has to be done without global or local variables; only indexes of start & end + array itself.
    Cannot get reasonable output & I'm not sure I have the right concept here, of using compression between array[pntrA] and *(++array).
    Code:
    int largest(int *array, int pntrA, int pntrB)
    {
    	if (pntrA==pntrB)
    		return array[pntrA];
    
    else
    	if (pntrA<pntrB)
    	{
    		
    			if (array[pntrA]<*(++array))
    			{
    				pntrA++;
    			return largest(array, pntrA, pntrB);	
    			}
    		else 
    			{
    				*(++array)=array[pntrA];
    				pntrA++;
    				return largest(array, pntrA, pntrB);
    			}
    						
    	}
    	return 0;
    }
    Help will be highly appreciated

  2. #2
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Assuming an unsorted array of course I would do something like this:
    Code:
    #include <stdio.h>
    
    int largest(const int *, int, int);
    
    int main(void)
    {
      int arr[] = { 1, 8, 29, 3, 9, 23, 94, 2, 9};
      printf("Largest: %d\n", largest(arr, 0, (sizeof arr / sizeof arr[0]) - 1));
      return 0;
    }
    
    int largest (const int *arr, int low, int high)
    {
      int mid, ret1, ret2;
      /* Since there is only one element it must be the highest */
      if ( low == high )
        return arr[low];
    
      /* Find the mid point of the array */
      mid = ((high - low) / 2) + low;
      /* Get the largest in the first half */
      ret1 = largest(arr, low, mid);
      /* Get the largest in the last half */
      ret2 = largest(arr, mid+1, high);
      /* Return the largest of the two values */
      return ret1 > ret2 ? ret1 : ret2;
    }
    The biggest problem I see with your code (besides formating) is that you have assignment statements that change the array. Since all you are doing is finding the largest value you should not change the values inside the array. To keep yourself from doing this change
    Code:
    int largest(int *array, int pntrA, int pntrB)
    to
    Code:
    int largest(const int *array, int pntrA, int pntrB)
    I think you were on the right track but it seems that you are assuming some type of sorting.

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    Nifty problem, that was a fun one. Here's my quickie attempt:
    Code:
    #include <stdio.h>
    
    int largest ( int a[], int l, int r )
    {
      if ( l == r - 1 )
        return l;
      
      r = largest ( a, l + 1, r );
    
      return a[r] > a[l] ? r : l;
    }
    
    int main ( void )
    {
      int a[] = {5, 4, 7, 2, 9, 7, 1, 0};
    
      printf ( "%d\n", a[largest ( a, 0, 8 )] );
    
      return 0;
    }
    p.s. I'm not nearly as inflexible as Mr. Sorted (Thantos).
    My best code is written with the delete key.

  4. #4
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Mine works on unsorted arrays Just look at my test array

    I'm gonna change mine to only take in two pointers

  5. #5
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >Mine works on unsorted arrays
    Heheh, I should take a reading for comprehension course. You said "assuming an unsorted array" and I read "assuming a sorted array". But you still didn't meet the requirements. It has to be done without local variables. Just the array and two index parameters. Othewise it would be too easy of a problem to be interesting.
    My best code is written with the delete key.

  6. #6
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Well I'll be a.... Yeah ok when you sign up for that course save me a spot also

  7. #7
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >when you sign up for that course save me a spot also
    Will do.
    My best code is written with the delete key.

  8. #8
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Oh one problem I've noticed with yours. It returns the position of the largest number where as the OP's code shows it returning the value.

  9. #9
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >It returns the position of the largest number where as the OP's code shows it returning the value.
    There was no mention of what the return type had to be, just that it should find the largest value in a one dimensional array.

    Ph34r the loophole!

    Anyway, it's a minor change to return the value instead of the index.
    My best code is written with the delete key.

  10. #10
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    In a much pretty and less user friendly package
    Code:
    int largest(int *arr, int l, int r)
    {
      if ( l == r )
        return arr[l];
    
      return arr[l] > (r=largest(arr, l+1, r)) ? arr[l] : r;
    }
    I still want to do a binary search method for it. They said no local variables but made no mention of no inline asm

  11. #11
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >In a much pretty and less user friendly package
    If you're going to compactisize code and kill the user experience, do it the right way:
    Code:
    int(o0)(int*o,int(O),int(Q)){return(O==Q-(1^0)?*(o+O):(Q=o0(o,O+(0^1),Q))>*(o+O)?Q:*(o+O));}
    My best code is written with the delete key.

  12. #12
    ---
    Join Date
    May 2004
    Posts
    1,379
    omg, prelude

  13. #13
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >omg, prelude
    That's just a simple obfuscation as the first wave. If everyone gets into it we can come up with something truly awful. Imagine three or four bored programmers trying their best to show up the last program by making it even more impenetrable.
    My best code is written with the delete key.

  14. #14
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    I've think we had that happen once. The results weren't pretty.

  15. #15
    Registered User
    Join Date
    Jun 2004
    Posts
    123

    Thumbs up

    Had I known before posting this problem, its going to be such a Fascinating duel...

    Thank you both Prelude & Thantos!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Find '&' character in char array?
    By tidemann in forum C Programming
    Replies: 7
    Last Post: 10-19-2006, 05:04 AM
  2. Quick question about SIGSEGV
    By Cikotic in forum C Programming
    Replies: 30
    Last Post: 07-01-2004, 07:48 PM
  3. Template Array Class
    By hpy_gilmore8 in forum C++ Programming
    Replies: 15
    Last Post: 04-11-2004, 11:15 PM
  4. Array Program
    By emmx in forum C Programming
    Replies: 3
    Last Post: 08-31-2003, 12:44 AM
  5. Help with an Array
    By omalleys in forum C Programming
    Replies: 1
    Last Post: 07-01-2002, 08:31 AM

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