What’s wrong with this Recursive Binary Search function?

Consider:

bool recur_search(int key, int values[], int lower, int upper)
{
    // base case 1: not in haystack
    if (upper < lower)
    {
        return false;
    }

    int mid = (lower + upper) / 2;

    // base case 2: found
    if (key == values[mid])
    {
        return true;
    }

    // recursive cases
    else if (key < values[mid])
    {
        recur_search(key, values, lower, mid - 1);
    }        
    else // (key > values[mid])
    {
        recur_search(key, values, mid + 1, upper);
    }

    // to get rid of "error: control may reach end of non-void function"
    return false;
}

What’s wrong with this code?

Classic mistake!

Even though it is calling itself correctly, it is missing the code necessary to recursively return the result. As it is written above, it will execute the recursive call to itself, but when it does find a number, it will return true on the first step back through the recursion. However, at the second step and thereafter, the code will return to the calling recursion and process the next line of code because it has no instruction to do something else. It will drop through the if(upper < lower) block and hit the return false statement. So, from there on, it will just return false back up the recursion.

The addition of one keyword, return, in two places, fixes the code:

 // recursive cases
...
    else if (key < values[mid])
    {
        return recur_search(key, values, lower, mid - 1);
    }        
    else // (key > values[mid])
    {
        return recur_search(key, values, mid + 1, upper);
    }
...