# Recursion

• 09-29-2002
MethodMan
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.
• 09-29-2002
Prelude
>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
• 09-29-2002
Nick
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.
• 09-30-2002
endo
Use code tags or Kermi3 will be after you!!!
• 09-30-2002
MethodMan
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
• 09-30-2002
Prelude
>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
• 09-30-2002
MethodMan
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?
• 09-30-2002
Nick
Quote:

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
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; }```