Thread: recursive linear search in C

  1. #1
    Registered User
    Join Date
    Jul 2015
    Posts
    5

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

  2. #2
    Registered User
    Join Date
    Sep 2007
    Posts
    1,012
    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.

  3. #3
    Registered User talahin's Avatar
    Join Date
    Feb 2015
    Posts
    51
    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

  4. #4
    Registered User
    Join Date
    Jul 2015
    Posts
    5
    Hello and thanks for responding in such detail, I really appreciate it!

    Quote Originally Posted by cas View Post
    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

  5. #5
    Registered User
    Join Date
    Jul 2015
    Posts
    5
    Quote Originally Posted by talahin View Post
    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;
    
    
    }

  6. #6
    Registered User talahin's Avatar
    Join Date
    Feb 2015
    Posts
    51
    Quote Originally Posted by mike1 View Post
    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

  7. #7
    Registered User
    Join Date
    Jul 2015
    Posts
    5
    Hello talahin,

    Thanks for your response.
    So if I understand you right, I'm actually forcing the recursive call once more than needed (7 times, instead of 6 to satisfy the condition of i > arrLen before 25 is returned .. but I don't seem to get an error for it.
    Does that mean I'm iterating over an area of memory that isn't actually allocated to the array?

    I suppose then I should change it to:

    Code:
    if(i >= arrLen) {
     
        return 25;
     
    }
    Does that sound right to you? Are you using a bounds-checker? I don't get any warnings or errors concerning this, and the program seems to work now, (i.e. it always returns if a value was found in the array, or not) but I guess the index is extending to i = 7 which is outside the bounds of the array!) Am I right in describing it this way?

    Quote Originally Posted by talahin View Post
    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
    Last edited by mike1; 07-22-2015 at 08:46 AM.

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,855
    Quote Originally Posted by mike1
    Does that sound right to you? (...) I don't get any warnings or errors concerning this, and the program seems to work now, (i.e. it always returns if a value was found in the array, or not) but I guess the index is extending to i = 7 which is outside the bounds of the array!) Am I right in describing it this way?
    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);
        }
    }
    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.

    You should check the return value of scanf.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Registered User
    Join Date
    Jul 2015
    Posts
    5
    Quote Originally Posted by laserlight View Post
    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?

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,855
    Quote Originally Posted by mike1
    I'm sorry could you explain this a bit more?
    Here is what the C standard says about fscanf, which also applies to scanf:
    Quote Originally Posted by C11 Clause 7.21.6.2 Paragraph 16
    The fscanf function returns the value of the macro EOF if an input failure occurs before the first conversion (if any) has completed. Otherwise, the function returns the number of input items assigned, which can be fewer than provided for, or even zero, in the event of an early matching failure.
    As such, we can take advantage of this to do some input error checking, e.g.,
    Code:
    if (scanf(" %d", &lookUpVal) == 1) {
        // ...
    }
    else {
        // Handle the input error
        // ...
    }
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linear Search
    By tsmith94 in forum C Programming
    Replies: 5
    Last Post: 10-16-2011, 09:33 PM
  2. Difference Between A Linear Search And Binary Search
    By ImBack92 in forum C Programming
    Replies: 4
    Last Post: 05-12-2011, 08:47 AM
  3. Linear search
    By kingkobra in forum C++ Programming
    Replies: 0
    Last Post: 12-03-2009, 02:42 PM
  4. binary search or linear search
    By vajira in forum C Programming
    Replies: 0
    Last Post: 06-05-2003, 12:42 PM
  5. Linear Search: the recursive way.
    By Nutshell in forum C Programming
    Replies: 7
    Last Post: 01-15-2002, 03:15 AM

Tags for this Thread