递归 C++ 函数不返回正确的布尔值

Question

如果该值是向量的前 n 个条目之一，则此函数应该返回 true，否则返回 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);
}

cout 之所以存在，是因为我不擅长调试。这是我测试的内容和结果：

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

很明显，函数正在寻找匹配值，但我非常困惑为什么它仍然返回 false。

Answer 1

您需要 return find

的结果

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

在你的函数中。

如果你打开警告，编译器会告诉你你做错了什么。

此外，您的基本情况似乎不正确。 0 是一个有效的索引。如果 n 是 -1，你应该停止。

关于您的问题，使用递归方法在连续容器中查找元素似乎很奇怪。为什么不试试

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

您可以将 find 的结果与 v.begin() + n 的结果进行比较，以检查是否找到该元素。

Answer 2

在这种情况下，您忘记从函数中 return

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() )

由于在此 if 语句中使用等于 v.size() 的无效索引

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

递归 C++ 函数不返回正确的布尔值

Recursive C++ function not returning correct boolean value

c++

recursion

search

vector

function-definition