# Thread: recursive linear search in C

1. ## 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) {
}
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. 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. 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. 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) {
}
else {
if (testArr[i] == searchVal) {
return i; // found!
}
else {
return recursiveLinearSearch(testArr, arrLen, i+1, searchVal);
}
}
}

"lcthw.c" 316L, 6812C written```

5. 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;

}```

6. 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

7. Hello talahin,

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?

Originally Posted by talahin
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

8. 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.

9. 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?

10. 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:
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
// ...
}```