Thread: recursive linear search in C

Hello, my first post.
I'm a complete novice, unfortunately, and just trying to put together what I can. I just seem to prefer C, even though everyone tells me to learn JS instead...

I'm reading an algorithms book, and it gave me some pseudocode for a recursive linear search, barebones, and I'm trying to construct it in C. This is my code so far, please what am I doing wrong? Because at the moment it keeps returning not-found(symbolised as number 25 here)...

If anyone cares to go through my code, I would appreciate any feedback, criticisms or suggestions - I just wanna get good at this.
One thing, if possible, could you please provide a solution that builds on what I've already written, instead of writing some Uber cool 5 lines genius piece that I probably won't understand! Thanks!

Code:

#include <stdio.h>


int recursiveLinearSearch(int testArr[], int arrLen, int i, int searchVal);


int main(int argc, const char *argv[])
{
        int testArr[] = {1,2,3,4,5,6};
        int arrLen = sizeof(testArr)/sizeof(testArr[0]);
        int result;
        int lookUpVal;
        int i;


        printf("%d\n", testArr[0]);
        printf("%d\n", arrLen);


        printf("Ok lets get started!\n");
        printf("Enter an integer to find in the mysterious array:");


        scanf(" %d", &lookUpVal);


        // printf("%d\n", lookUpVal);


        result = recursiveLinearSearch(testArr, arrLen, i, lookUpVal);


        printf("%d\n", result);


        return(0);
}


int recursiveLinearSearch(int testArr[], int arrLen, int i, int searchVal) {
        if (i > arrLen) {
                return 25; // 25 = not found
        }
        else if (i <= arrLen && testArr[i] == searchVal) {
                return i; // found!
        }
        else if (i <= arrLen  && testArr[i] != searchVal) {
                return recursiveLinearSearch(testArr, arrLen, i+1, searchVal);
        }
}

You're not giving “i” a value, so it's filled with garbage. A good modern compiler (e.g. gcc or clang) can warn about this:

Code:

t.c: In function 'recursiveLinearSearch':
t.c:50:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
t.c: In function 'main':
t.c:30:16: warning: 'i' is used uninitialized in this function [-Wuninitialized]
         result = recursiveLinearSearch(testArr, arrLen, i, lookUpVal);

That's gcc 5.2.0 with the -Wall flag. If you're using gcc or clang, always build with at least -Wall, which enables a lot of warnings (not all, despite its name).

The other warning is due to the fact that gcc isn't able to determine that you are always returning a value, because the conditions are a bit muddled. I find it a bit unclear, too, compared to how it might look:

Code:

if(i > arrLen) {
    return 25;
} else {
    if(testArr[i] == searchVal) {
        return i;
    } else {
        return recursiveLinearSearch(testArr, arrLen, i + 1, searchVal);
    }
}

That is,

Code:

if(foo) {} else {}

is generally easier to quickly parse than

Code:

if(foo) {} else if(!foo) {}

even though they do the same thing. That's because you don't have to look carefully to compare the two conditions. Once you've seen “foo”, you know that “else” is “not foo”. Especially, as in your code, when the conditions are more complex (e.g. using &&) it becomes more burdensome to read, and you are going to be more likely to introduce a bug if you have to change two conditions instead of one. I had to look carefully to make sure gcc wasn't right.

Remember that in your case the array index goes from 0 to 5.

Code:

if(i > arrLen) {

    return 25;

} else {

    if(testArr[i] == searchVal) {

        return i;

    } else {

        return recursiveLinearSearch(testArr, arrLen, i + 1, searchVal);

    }

}

but when i == 6 this code will try to compare testArr[6] against the search value. This will result in a out of bounds error.

Cheers

Hello and thanks for responding in such detail, I really appreciate it!

Originally Posted by cas

You're not giving “i” a value, so it's filled with garbage. A good modern compiler (e.g. gcc or clang) can warn about this:

Code:

t.c: In function 'recursiveLinearSearch':
t.c:50:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
t.c: In function 'main':
t.c:30:16: warning: 'i' is used uninitialized in this function [-Wuninitialized]
         result = recursiveLinearSearch(testArr, arrLen, i, lookUpVal);

That's gcc 5.2.0 with the -Wall flag. If you're using gcc or clang, always build with at least -Wall, which enables a lot of warnings (not all, despite its name).

Thanks for this! I thought I was using the -Wall flag, I tried to make a Makefile that looked like this:

Code:

CFLAGS=-Wall -g


all:
        gcc -o p lcthw.c
        ./p


clean:
        rm -r p

which enabled me to just type 'make' ... but it wasn't including the -Wall flag... so I changed it instead to:

Code:

all:
        gcc -Wall -g -o p lcthw.c
        ./p


clean:
        rm -r p

... which works now, but would you know how to use the CFLAGS=-Wall correctly?

The other warning is due to the fact that gcc isn't able to determine that you are always returning a value, because the conditions are a bit muddled. I find it a bit unclear, too, compared to how it might look:

Code:

if(i > arrLen) {
    return 25;
} else {
    if(testArr[i] == searchVal) {
        return i;
    } else {
        return recursiveLinearSearch(testArr, arrLen, i + 1, searchVal);
    }
}

That is,

Code:

if(foo) {} else {}

is generally easier to quickly parse than

Code:

if(foo) {} else if(!foo) {}

even though they do the same thing. That's because you don't have to look carefully to compare the two conditions. Once you've seen “foo”, you know that “else” is “not foo”. Especially, as in your code, when the conditions are more complex (e.g. using &&) it becomes more burdensome to read, and you are going to be more likely to introduce a bug if you have to change two conditions instead of one. I had to look carefully to make sure gcc wasn't right.

Yes you are totally right, it's much better that way thanks.
The algorithms book specified these exact conditions in the pseudocode to be precise I guess, but it's not necessary in the final code ...

So it works now, thanks a lot ... the final code is:

Code:

#include <stdio.h>


int recursiveLinearSearch(int testArr[], int arrLen, int i, int searchVal);


int main(int argc, const char *argv[])
{
        int testArr[] = {1,2,3,4,5,6};
        int arrLen = sizeof(testArr)/sizeof(testArr[0]);
        int result;
        int lookUpVal;
        int i = 0;


        printf("%d\n", testArr[0]);
        printf("%d\n", arrLen);


        printf("Ok lets get started!\n");
        printf("Enter an integer to find in the mysterious array:");


        scanf(" %d", &lookUpVal);


        // printf("%d\n", lookUpVal);


        result = recursiveLinearSearch(testArr, arrLen, i, lookUpVal);


        printf("%d\n", result);


        return(0);
}


int recursiveLinearSearch(int testArr[], int arrLen, int i, int searchVal)
{
        if (i > arrLen) {
                return 25; // 25 = not found
        }
        else {
                if (testArr[i] == searchVal) {
                        return i; // found!
                }
                else {
                        return recursiveLinearSearch(testArr, arrLen, i+1, searchVal);
                }
        }
}


"lcthw.c" 316L, 6812C written

Originally Posted by talahin

Remember that in your case the array index goes from 0 to 5.

Code:

if(i > arrLen) {

    return 25;

} else {

    if(testArr[i] == searchVal) {

        return i;

    } else {

        return recursiveLinearSearch(testArr, arrLen, i + 1, searchVal);

    }

}

but when i == 6 this code will try to compare testArr[6] against the search value. This will result in a out of bounds error.

Cheers

Hello thanks for replying. I don't quite understand, I thought the first IF condition should account for i == 6

Code:

if(i > arrLen) {


    return 25;


}

Originally Posted by mike1

Hello thanks for replying. I don't quite understand, I thought the first IF condition should account for i == 6

Code:

if(i > arrLen) {

    return 25;

}

Your array has 6 items, so your arrLen has the value 6. These 6 items are indexed 0..5.
With i == 6 and arrLen == 6 the check 6 > 6 will be false not true.
So it will skip the return 25; statement.

Cheers

Originally Posted by laserlight

Yes.

You should avoid using magic numbers like 25 by defining a named constant. You can also simplify the style of the if-else chain, e.g.,

Code:

#define NOT_FOUND 25

// ...

int recursiveLinearSearch(int testArr[], int arrLen, int i, int searchVal)
{
    if (i >= arrLen) {
        return NOT_FOUND;
    }
    else if (testArr[i] == searchVal) {
        return i; // found!
    }
    else {
        return recursiveLinearSearch(testArr, arrLen, i + 1, searchVal);
    }
}

OK THANKS FOR THE TIP!

Incidentally, while 25 might work for your practice purpose, in practice it is more conventional to return a -1 or the length of the array (i.e., arrLen) to indicate not found.

Thanks for letting me know the convention, will do!

You should check the return value of scanf.

I'm sorry could you explain this a bit more?