Thread: Recursion

Ive been trying to write a pseudo code function to recusively look for the smallest item in an array, but how do I set up a variable to hold the smallest element, without reseting it

Smallset(A, j, k) // A = array, j - first element, k - last element
{
(test to see if empty)
(if so exit)
smallest = ? // dont know what to set this too
if(k < smallest)
k == smallest;
else
Smallest(A, j+1, k)

return smallest
}

Didnt know where to post this.

Do you see the problem, it will just clober it if I set it to 0.

>Do you see the problem
Have you tried using the smallest variable as a parameter to the recursive function?:

Code:

int find_min ( int *a, int min, int count )
{
  if ( count > 0 ) {
    if ( *a < min )
      min = find_min ( a + 1, *a, count - 1 );
    else
      min = find_min ( a + 1, min, count - 1 );
  }

  return min;
}

It would be called like this with an array of 8 items:

val = find_max ( array, array[0], 8 );

-Prelude

I general you can do something like
#define NOT_FOUND INT_MAX
has a sentinel.

But in this case just
stop the recursion when there's one element. Then
that one elemen is the smallest. I think if I understand
what you want to do is this

Code:

smallest(A, i, j)
    if (i >= j)
        return A[i]
    q = (i + j) / 2
    left = smallest(A, i, q)
    right = smallest(A, q + 1, j)
    if (A[left] <= A[right])
         return A[left]
    else 
         return A[right}
}

[edited by ygfperson for code tags]
This solution is O(n) the same as doing it linearly.

Use code tags or Kermi3 will be after you!!!

Thanks for the help, the code does its purpose. Just a few questions regarding the code.

*a < min

is that a reference to the first position in the array?

find_min(a +1, *a, count -1)
what does the a +1 do?

*a points to the array again?

and the count -1, goes down from the end by one?

Thanks

>is that a reference to the first position in the array?
a is a pointer, by dereferencing it you get the contents of the current element.

>what does the a +1 do?
a is a pointer , by recursing with the a + 1, you pass address of the next element in the array.

>and the count -1, goes down from the end by one?
Correct, this is so that the function knows when to stop.

-Prelude

Thanks for the clarifications
Im doing a call trace, and I got to *a < min, what is min set to the first time it compares this?

Is it just some piece of memory?