min value@array@recursion: works only upto a certain array size

[somjit{}]

this code gives the correct result upto size 6 (i'v run this a few times, and 6 seems to be the boundary), although the intermediate steps are all insane! then onwards, from size 7, it returns minimum value 0

/*minimum of an array using recursion*/

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

int findMin(int* arr,int min,int size);
int* populateArray(int size); 
void printArray(int* arr,int size);
int main(){

    int i=0,size=0,min=0;
    int* arr;

    printf("enter size of array: ");
    scanf("%d",&size);

    arr=populateArray(size);

    printf("array is: ");
    printArray(arr,size);

    min=*(arr+0);

    min=findMin(arr,min,size);
    printf("\n\nthe min value in the arr is: %d\n",min);

    return 0;   

}

int* populateArray(int size){
    int i=0;
    int* arr;

    arr=(int*)malloc(sizeof(int)*size);

    srand(time(NULL)); 
    for(i=0;i<size;i++){
        *(arr+i)=(rand()%1000); 
    }   
    return arr;
}

void printArray(int* arr,int size){

    int i;
    for(i=0;i<size;i++)
    printf("%d ",*(arr+i));
    puts("\n");
}


int findMin(int* arr,int min,int size){

    printf("in findMin() : passed values >> array:%d  min:%d  size:%d\n",*(arr),min,size);
    static int j=1;

    if(j==size){
        return min; 
    }
    else if(min>*(arr+j)){
        min=*(arr+j);
        j++;
        findMin((arr+j),min,size);  
    }
    else if(min<*(arr+j)){
        j++;
        findMin((arr+j),min,size);
    }

}

i cant understand why this is so... :(
any help regarding the matter would be great. :)

regards
somjit.

[aswekown]

try this way:

int main(int argc, char **argv)
{
    int m;
    int arr[6] = {1, 8, 7, 3, 100, 120};

    m = f_min(arr, 6);
    printf("The MIN values is -->%d\n", m);

    return 0;
}
int f_min(int arr[], int i)
{
    int m;
    if (i==0)
    {
        return arr[0];
    }
    else
    {
        m = f_min(arr, i-1);
        if (m > arr[i])
        {
            return arr[i];
        }     
        else
        {
            return m;
        }
    }
}

[deceptikon]

Your findMin() has two problems, one is a bug and another is a usability problem. The bug is that you're moving the pointer ahead by j steps on every recursive call, but you're also using j as an index into the array. This is basically a guaranteed access out of bounds. Either use j to access the array, or move the pointer ahead by 1 each time:

/* Option 1: Use a static index */
int findMin(int *arr, int min, int size)
{
    printf("in findMin() : passed values >> array:%d  min:%d  size:%d\n", *(arr), min, size);

    static int j = 1;

    if (j == size){
        return min; 
    }
    else if (min > arr[j]){
        min = arr[j++];
        return findMin(arr, min, size);  
    }
    else {
        j++;
        return findMin(arr, min, size);
    }
}

/* Option 2: Adjust the pointer */
int findMin(int *arr, int min, int size)
{
    printf("in findMin() : passed values >> array:%d  min:%d  size:%d\n", *(arr), min, size);

    if (size == 0)
        return min; 

    if (min > *arr)
        min = *arr;

    return findMin(arr + 1, min, size - 1);
}

The second option is recommended because using a static variable makes your function non-reentrant. In other words, you can only find the minimum element of an array one time. Any subsequent calls will continue to increment the index. That issue with the static variable is your usability problem.

[somjit{}]

@deceptikon : thank you :) i see where i made the mistake. you providing the solution with two different methods was really helpful :)
only small thingy left here is that in the 2nd method, the one you suggested, the loop is doing one extra iteration at the end.
im hoping i can fix it on my own though...
as for now, the problem is solved.

[deceptikon]

only small thingy left here is that in the 2nd method, the one you suggested, the loop is doing one extra iteration at the end.

That's the base case where size is 0. The only reason it's "bad" in this case is because of the debug printf() accessing the array out of bounds, but the algorithm is otherwise correct. If you "fix" the problem then you'll end up with an algorithm that fails to find the smallest value when it's the last one in the array.

The correct fix would be to avoid dereferencing the array until after it's confirmed that recursion hasn't reached the base case:

int findMin(int *arr, int min, int size)
{
    if (size == 0) {
        printf("in findMin() : passed values >> min:%d  size:%d\n", min, size);
        return min;
    }

    printf("in findMin() : passed values >> array:%d  min:%d  size:%d\n", *(arr), min, size);

    if (min > *arr)
        min = *arr;

    return findMin(arr + 1, min, size - 1);
}

But these debug printf() calls should be either removed or conditionally excluded anyway, because you don't want to see them once you're confident that the function works as intended.

[somjit{}]

@deceptikon :
i just noticed that u were decrementing size on each recursion... i only kept that to check initially if the passed array was valid or not, but the decremented size makes it a checking condition for whether the recursion has reached the base case as well! (atleast thats what i think it does.. :| ) i wish i had thought of that. :(

i had some exams on networking at college, so couldnt concentrate on programming as much i would want to, probably the reason it took me a week to notice that nice trick...
but thanks a lot for your detailed answers, i always learn a lot from them :)

regards.