Recursive Bool Function "skipping" return

Question

I've been breaking off the rust with C coding, and have been working on an exercise in sorting and searching; in particular, binary searching using recursion. I am getting unexpected results, as when my binary search function does find the value it's looking for, it "should" return true, but instead skips to the final possible "return false" instruction. In the below, I've shared the code, as well as printed output to demonstrate how a particular value in a sorted array is identified, yet still resulting in a 'false' being returned.

There is one exception to all this... If the searched for value happens to be the midpoint value contained in the middle element of the entire, original array, such that its found during the very first execution of the binSearch function, it returns true as expected. It is only when subsequent recursive calls are made that a successful find still results in a return false to the function that calls the binary search function.

Code as follows;passed array is already sorted least to greatest:

bool binSearch(int value, int values[], int up, int down)
{
    int midElement = (up-down)/2 + down;
    int midValue = values[midElement];
    printf("Midvalue now equals: %i\n", midValue);

    if(up >= down)
    {
        if(value == midValue)
        {    
            printf("Found '%i' at element '%i': ", midValue, midElement);
            return true; //This gets skipped, even when printf shows the find
        }
        else if(value > midValue)
            binSearch(value, values, up, midElement+1);
        else if(value < midValue)
            binSearch(value, values, midElement-1, down);
    }
    return false;
}

Sample Output -- Note that "Didn't find the value" is what the function that calls binSearch will printout if its receives a false.

Current Value: 1222
Current Value: 9601
Current Value: 46592
Current Value: 64187
Current Value: 64657
Midvalue now equals: 46592
Midvalue now equals: 1222
Midvalue now equals: 9601
Found '9601' at element '1'
Didn't find the value.

Sample output when the searched for value is in the middle of the entire array -- This is the one exception where true is returned as expected.

Current Value: 1222
Current Value: 9601
Current Value: 46592
Current Value: 64187
Current Value: 64657
Midvalue now equals: 46592
Found '46592' at element '2':
Found the value.

I'm theorizing that there must be some problem with how results from 2nd generation onward recursive function calls are getting passed to the original caller (or rather, not getting passed back at all)...

Thank you for any insights into what might be happening here.

What should happen when a recursive call returns `true`? When it returns `false`? Right now you don't even *check* what the recursive calls returns. Right now I suggest you read [How to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) by Eric Lippert, because with a very small amount of time in a debugger you would have found out the problem in much shorter time than it took to write and post this question. — Some programmer dude, Jul 23 '17 at 20:40

score 0 · Accepted Answer · answered Jul 23 '17 at 20:48

Your function binSearch returns a boolean for each call. Make sure you return the boolean value when the recursion collapses. i.e.

else if(value > midValue)
    return binSearch(value, values, up, midElement+1);
else if(value < midValue)
    return binSearch(value, values, midElement-1, down);

Recursive Bool Function "skipping" return

1 Answers1