PDA

View Full Version : Recursion



MethodMan
09-29-2002, 07:55 PM
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.

Prelude
09-29-2002, 08:16 PM
>Do you see the problem
Have you tried using the smallest variable as a parameter to the recursive function?:


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

Nick
09-29-2002, 11:22 PM
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


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.

endo
09-30-2002, 05:03 AM
Use code tags or Kermi3 will be after you!!!

MethodMan
09-30-2002, 07:50 PM
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

Prelude
09-30-2002, 08:17 PM
>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

MethodMan
09-30-2002, 08:26 PM
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?

Nick
09-30-2002, 08:33 PM
Use code tags or Kermi3 will be after you!!!

Only for code that is in c++ and will run correctly.
Since the code I gave is neither I suppose I don't
have to use code tags.

Here is some correct code


#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 100

int smallest(int A[], int i, int j)
{
int q;
int left, right;

if (i >= j)
return A[i];

q = (i + j)/2;
left = smallest(A, i, q);
right = smallest(A, q + 1, j);
if (left < right)
return left;

return right;
}

int main(void)
{
int A[N];
int i;

srand(time(NULL));
for (i = 0; i < N; ++i)
{
A[i] = rand() % N;
printf("%3d ", A[i]);
if ((i + 1) % 12 == 0)
printf("\n");
}
printf("\n");
printf("smallest = %d\n", smallest(A, 0, N - 1));

return 0;
}