Recursive C++ function not returning correct boolean value

Question

This function is supposed to be returning true if the value is one of the first n entries of a vector and false if it isn't. I've been working on this for a while and can't figure out why it isn't working correctly.

template <class T>
bool find(const vector<T> &v,  T value, int n) {
    //base case
    if (n == 0) {
        cout << "not here" << endl;
        return false;
    }
    //general case
    if (v[n] == value) {
        cout << v[n] << " == " << value << endl;
        return true;
    }
    cout << "find(" << "v" << ", " << value << ", " << n - 1 << ")" << endl;
    find(v, value, n - 1);
}

The couts are only there because I suck at debugging. Here's what I tested it with and the results:

vector<int> v = {1, 2, 3, 4, 5};
cout << boolalpha << find(v, 3, 4);

Console:

find(v, 3, 3)
find(v, 3, 2)
3 == 3
false

Clearly, the function is finding the matching value, but I'm extremely confused why it's still returning false anyway.

what does the function return if neither n==0 nor v[n] == value ? — 463035818_is_not_an_ai
– 463035818_is_not_an_ai, Commented Apr 12, 2020 at 22:01
Besides the missing return, your function never looks at v[0], and so will never find the value if it happens to be in the first element. Recall that the first three elements are v[0], v[1] and v[2]; but not v[3]. — Igor Tandetnik
– Igor Tandetnik, Commented Apr 12, 2020 at 22:02
why not use a for loop? It is not really necessary here to have a recursive function and a loop is much easier to read — goaran
– goaran, Commented Apr 12, 2020 at 22:04
@goaran if this isnt an exercise std::find should be used. — 463035818_is_not_an_ai
– 463035818_is_not_an_ai, Commented Apr 12, 2020 at 22:07
It is not unreasonable for a vector to hold thousands, and possibly millions of elements. Writing a recursive find function for such a container is nonsensical, since you would run out of stack space trying to find the element. — PaulMcKenzie
– PaulMcKenzie, Commented Apr 12, 2020 at 22:10

cigien · Accepted Answer · 2020-04-12 22:19:28Z

3

You need to return the result of find

return find(v, value, n - 1);

in your function.

If you turn on warnings, the compiler will tell you you're doing something wrong.

Also, your base case seems incorrect. 0 is a valid index. You should stop if n is -1.

Related to your question,using a recursive approach to find an element in a contiguous container seems odd. Why don't you just try something like

std::find(v.begin(), v.begin() + n, value);

You can compare the result of find to v.begin() + n to check if the element is found.

edited Apr 12, 2020 at 22:19

answered Apr 12, 2020 at 22:01

cigien

61.2k11 gold badges86 silver badges124 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Vlad from Moscow · Accepted Answer · 2020-04-12 23:30:29Z

You forgot to return from the function in this case

find(v, value, n - 1);

Nevertheless the function in any case is defined incorrectly.

It should look like

template <class T>
bool find( const std::vector<T> &v,  const T &value, typename std::vector<T>::size_type n ) 
{
    return v.size() < n || n == 0 ? false : v[n-1] == value || find( v, value, n - 1 );
}

Here is a demonstrative program.

#include <iostream>
#include <iomanip>
#include <vector>

template <class T>
bool find( const std::vector<T> &v,  const T &value, typename std::vector<T>::size_type n ) 
{
    return v.size() < n || n == 0 ? false : v[n-1] == value || find( v, value, n - 1 );
}

int main() 
{
    std::vector<int> v = { 1, 2, 3, 4, 5 };

    std::cout << std::boolalpha << find( v, 5, v.size() ) << '\n';
    std::cout << std::boolalpha << find( v, 5, v.size() - 1 ) << '\n';
    std::cout << std::boolalpha << find( v, 1, 1 ) << '\n';
    std::cout << std::boolalpha << find( v, 2, 1 ) << '\n';

    return 0;
}

Its output is

true
false
true
false

As for your function implementation then it will have undefined behavior for example for this call

find( v, 5, v.size() )

due to using an invalid index equal to v.size() in this if statement

if (v[n] == value) {
    cout << v[n] << " == " << value << endl;
    return true;
}

Actually the user can specify the third argument greater than the size of the array. So a more flexible approach is to allow the user ti specify any value for the third argument but perform the search among existent elements of the vector. Here is such a function definition.

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>

template <class T>
bool find( const std::vector<T> &v,  const T &value, typename std::vector<T>::size_type n ) 
{
    n = std::min( n, v.size() );
    return n != 0 && ( v[n-1] == value || find( v, value, n - 1 ) );
}

int main() 
{
    std::vector<int> v = { 1, 2, 3, 4, 5 };

    std::cout << std::boolalpha << find( v, 5, 6 ) << '\n';
    std::cout << std::boolalpha << find( v, 5, 4 ) << '\n';

    return 0;
}

The program output is

true
false

Collectives™ on Stack Overflow

Recursive C++ function not returning correct boolean value

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related