递归并返回布尔值

bool binsearch(string phrase, vector<string> words, int from, int to, int &test)
{
    while (tf == \"y\") //tf is a global variable
    {
        int mid = (to+from)/2;
        if (words[mid] == phrase) {tf = \"t\"; return true;}
        if (mid == test) {tf = \"f\"; return false;}
        if (words[mid] > phrase) {return binsearch(phrase, words, mid-1, to, mid);}
        else {return binsearch(phrase, words, from, mid+1, mid);}
     }
}

我正在努力使此二进制搜索正常工作。我需要整体函数返回\“ true \”或\“ false \”。我了解递归如何工作，直到第6行或第7行执行并调用return命令。我已经进行了研究，似乎无法退出该功能，它必须自己“展开”。 tf全局变量是无意义的，因此它在展开时不会再次执行该主体...但是我仍然没有得到我想要的结果。本质上，我只想在调用return true或return false命令后尽快退出函数，并相应地将值返回给主函数谢谢

已邀请:

7 个回复

妒垮

我也不理解您的二进制搜索，除了递归之外使用全局变量会导致程序难以理解。最好再次返回调用堆栈，然后正确地“展开”它。请看以下示例（未经测试）：

bool binsearch(const string& phrase, const vector<string> &words, int from, int to)
{
    if (from > to)
        return false; // word not found
    int mid = from + (to - from) / 2; // i think your calculation is wrong here
    int cmp = phrase.compare(words[mid]);
    if (cmp < 0)
        return binsearch(phrase, words, from, mid - 1);
    else if (cmp > 0)
        return binsearch(phrase, words, mid + 1, to);
    else
        return true; // word found
}

赐黄

您可以按以下方式使用STL的内置binary_search：

binary_search(words.begin(),words.end(), phrase)

如果您这样做是为了学习；有几件事... 您不需要while循环。需要考虑三种情况：单词出现在mid之前，at3处或mid之后。这三种情况中的每一种都是return-因此甚至不可能到达循环体的末端。您恰好使用test，是否需要此变量？您应该仔细考虑仍然需要搜索的索引范围。 from和to是包容性的还是排斥性的？您需要保持精确和一致。考虑正整数的除法取整。无论它们具有什么值，请确保递归调用的范围较小-避免无限循环。这将有助于避免使用您的test变量（请参见下面的David注释）。使用全局变量不是一个好习惯；当然不是在纯函数中-我假设您是出于调试目的而这样做？ to和from的大小是多少？在某些情况下，请注意to+from可能会超过2^31-1。在C ++中，通常使用迭代器来表达这些概念。当然，您不必。在C ++中，通常会在可能的情况下将大对象传递15个字符-这样，递归调用就不需要复制整个向量。这对于正确性并不重要，但对于有效代码而言实际上非常重要。

僻朵庙惩竣

将vector<string> words作为您的17ѭ函数的参考。目前，无论何时调用不需要的函数，它都会继续创建vector<string>的副本。而且，将来如果您要更新vector <>，则最好通过引用传递。 while循环外应有return语句。那将是最后的\'return`。

芦歉竭皑

摆脱这种情况的经典方法之一：无需递归即可重写它。例如，使用while循环，然后在找到结果后立即使用break出去。您可以看一下以下代码（未编译，只是通过您自己的代码快速编写而成）

bool binsearch(const string& phrase, const vector<string> &words, int from, int to)
{
    bool retVal = false;
    int start = from;
    int end = to;


    while(start<end) {
       int mid = from + (to - from) / 2; // i think your calculation is wrong here
       int cmp = phrase.compare(words[mid]);
       if (cmp < 0) {
           end=mid-1;
       } else if (cmp > 0) {
           start=mid+1;
       } else {
           retVal = true;
           break;
       }
    }
    return retVal;
}

没有优雅或便携式的方法可以跳出完整的调用堆栈，充其量是相当冒险的。此外，去递归化的函数将更快：它不需要将内容压入堆栈并进行函数调用编辑添加了缺失的回报关于表演：进行基准测试。在这种特殊情况下，（对于人类读者而言）代码复杂度几乎是相同的，但是根据算法的不同，它可能更加复杂（甚至不可能）。

烷刨画颠离

您的代码有几处错误。对于初学者，尚不清楚to和from是什么意思：它们是否具有包容性，或者独家。如果两者都包含在内（您的论点似乎建议递归调用），如何检测结束。 test是什么意思？您似乎正在将其用作没有找到单词，但我不知道怎么做时结束准则。如果我正在写这篇文章，我将使用一个简单的帮助器类来保存目标和单词列表（但您可以传播它们显式关闭）和包装函数，以便客户端代码不必指定to和from参数。有不需要全局变量或任何其他的“ 7”。和我将使用C ++中惯用的半开间隔：低包括边界，包括边界上限（所以top == bottom 指定了一个空范围，因此我已经完成但没有找到元件）：

bool 
binSearch( std::string const& target,
           std::vector<std::string> const& words );

namespace {

    class BinSearcher
    {
        std::vector<std::string> const& myWords;
        std::string const& myTarget;

        bool doSearch( int bottom, int top ) const
        {
            int mid = (top - bottom) / 2;
            return mid != top
                && (myTarget == myWords[mid]
                    || (myTarget > myWords[mid] && doSearch( mid + 1, top ))
                    || (myTarget < myWords[mid] && doSearch( bottom, mid ));
        }
        BinSearcher( std::string const& target,
                     std::vector<std::string> const& words )
            : myWords( words )
            , myTarget( target )
        {
        }
        friend bool binSearch( std::string const&,
                               std::vector<std::string> const& );
    };
}

bool 
binSearch( std::string const& target,
           std::vector<std::string> const& words )
{
    BinSearcher searcher( target, words );
    return searcher.doSearch( 0, words.size() );
}

请注意，在测试范围不相等；如果所有都将导致超出范围的访问的元素少于目标。另外：我认为您正在这样做是出于教学上的原因。否则，您应该只使用标准中的功能图书馆。而且我通常不会在这里使用递归：一个简单的迭代解决方案：

namespace {

    bool
    doBinSearch( std::string const& target,
                 std::vector<std::string> const& words,
                 int bottom,
                 int top )
    {
        bool found = false;
        while ( bottom != top && ! found ) {
            int mid = (top - bottom) / 2;
            int cmp = target.compare( words[mid] );
            if ( cmp < 0 ) {
                top = mid ;
            } else if ( 0 < cmp ) {
                bottom = mid + 1;
            } else {
                found = true;
            }
        }
        return found;
    }
}

bool
binSearch( std::string const& target,
           std::vector<std::string> const& words )
{
    return doBinSearch( target, words, 0, words.size() );
}

（最后，您会注意到我已经将您的参数转换为参考。它不会改变逻辑上的任何东西代码，但是如果words比较大，它将使对性能有重大影响。）

凸晴

您可以使用longjmp（也称为\“ non-localgoto\”）立即退出内部递归，但问题是这种微优化是否值得解决。更好的选择是将递归更改为循环。由于所有递归调用都位于“尾位置”（是return的参数），因此您可以将其替换为重置参数变量的代码。不幸的是，我不了解您的代码，因此无法举一个例子。

硕歌沙

这是使用递归的经典练习-当然，人们也可以非递归地做事，但是“让递归管理一个人的簿记工作”非常优雅。 ”，我建议对合并排序或快速排序进行类似的练习。递归结构非常相似，但是在递归上下文中极大地简化了簿记。在现代CPU上，递归代码令人惊讶！ -通常以更快的速度启动。这是我使用OP问题的上下文的递归实现。请注意，没有必要单独测试中点元素：在C ++“小于\”范式的上下文中，用于比较谓词（在给定<的情况下，可以通过.not。（a.lt.b）和..not。（b.lt.a）），对中点的相等性进行额外的测试几乎没有意义，尽管在字符串类及其多值比较结果的特殊情况下，它可能会产生适度的加速比对0返回结果的特殊处理。我的示例版本仅假定<（在某种意义上，如果一个人实际上仅具有<，则将稍微重新分配使用该条件的分治法），这将更容易地归纳为数字和用户定义的数据类型：

bool binsearch(const string&phrase, vector<string>&words, int from, int to)
{
    if(from > to) return false;    // range sanity check
    if(from == to) return (phrase.compare(words[to]) == 0);    // bottom of the recursion
    int mid = from + (to-from)/2;        // Range still has >= 2 elements; set up to recurse
    if(phrase.compare(words[mid]) <= 0)  // Recurse into the subinterval bracketing the target
        return binsearch(phrase,words, from,mid);
    else
        return binsearch(phrase,words, mid+1,to);
}

这是上述内容的非递归版本，它纠正了用户\'Bruce \'发布的示例代码中的几个问题，并且再次不使用单独的中点值测试：

bool binsearch_nr(const string& phrase, const vector<string> &words, int from, int to)
{
    if(from > to) return false;    // range sanity check
    while(from < to) {
        int mid = from + (to-from)/2;
        int cmp = phrase.compare(words[mid]);
        if (cmp <= 0)
            to = mid;
        else
            from = mid+1;
    }
    return (phrase.compare(words[to]) == 0);
}

我使用了100万个准随机文本摘要（在Mac OS上使用gcc 4.2构建的代码）对上述2种实现方式进行了比较计时...递归版本的运行速度降低了约20％。但是，对于我手推的合并排序代码，递归速度更快。 YMMV。

要回复问题请先登录或注册

递归并返回布尔值

7 个回复

发起人

search

recursion

c++

binary

boolean

问题状态

递归并返回布尔值

与内容相关的链接

7 个回复

发起人

search

recursion

c++

binary

boolean

问题状态