Рекурсивная функция C ++ не возвращает правильное логическое значение

Question

Предполагается, что эта функция возвращает значение true, если значение является одним из первых n элементов вектора, и значение false, если это не так. Я работал над этим некоторое время и не могу понять, почему он работает неправильно.

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

Коты есть только потому, что я отстой в отладке. Вот то, что я проверил, и результаты:

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

Консоль:

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

Ясно, что функция находит соответствующее значение, но я очень запуталась, почему она все еще возвращает ложь в любом случае.

Answer 1

Вам необходимо вернуть результат find

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

в вашей функции.

Если вы включите предупреждения, компилятор скажет вам, что вы что-то делаете не так.

Кроме того, ваш базовый случай кажется неверным. 0 является действительным индексом. Вам следует остановиться, если n равно -1.

По вашему вопросу использование рекурсивного подхода для поиска элемента в непрерывном контейнере кажется странным. Почему бы вам просто не попробовать что-то вроде

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

Вы можете сравнить результат find с v.begin() + n, чтобы проверить, найден ли элемент.

Answer 2

Вы забыли вернуться из функции в этом случае

find(v, value, n - 1);

Тем не менее функция в любом случае определена неправильно.

Она должна выглядеть как

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

Вот демонстрационная программа.

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

Выходные данные:

true
false
true
false

Что касается реализации вашей функции, то она будет иметь неопределенное поведение, например, для этого вызова

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

из-за использования недопустимого индекса, равного v.size(), в этом операторе if

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

Фактически пользователь может указать третий аргумент, превышающий размер массива. Таким образом, более гибкий подход состоит в том, чтобы позволить пользователю указать любое значение для третьего аргумента, но выполнить поиск среди существующих элементов вектора. Вот такое определение функции.

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

Вывод программы:

true
false