递归＆返回布尔值

Question

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行执行并且返回命令被调用。我已经完成了研究，似乎没有办法退出这个功能，它必须“放松”自己。 tf全局变量废话是这样的，它不会再次执行该机构，当它展开...但我仍然没有得到我想要的结果。

基本上，我只是想离开的功能无论是回归后尽快真或返回假命令被调用，值返回到主函数相应

感谢

Answer 1

我不明白你的二分搜索，除了递归之外使用全局变量导致程序很难理解。最好再次返回调用堆栈并正确“放开”它。看下面的例子（未经测试）：

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 
} 

Answer 2

可以使用STL的内置​​如下：

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

如果你这样做是为了学习;有几件事...

• 你不需要while循环。有三种情况需要考虑：单词在mid之前，在mid之前或在mid之后。这三种情况中的每一种return s - 因此甚至不可能达到循环体的末端。
• 您使用test时刚好，你需要这个变量吗？
• 您应该仔细考虑究竟是哪些索引范围仍然需要搜索。 是from和to包含或排他？你需要精确和一致。
• 考虑正整数的划分舍去。不管他们具有什么样的价值，确保递归调用调用较小的范围 - 以避免无限循环。这将有助于避免需要变量test（请参阅下面的David的评论）。
• 使用全局变量是不好的做法;当然不是其他纯函数 - 我假设你正在做这个调试目的？
• to和from可以多大？在某些情况下，请注意to+from可能会超过2^31-1。
• 在C++中用迭代器表达这些概念是很典型的。当然，你不必这样做。
• 在C++中，在可能的情况下通过const &传递大对象是很典型的 - 这样，递归调用就不需要复制整个向量。这对正确性并不重要，但对于高效的代码来说非常重要。

Answer 3

可以使用longjmp，又名“非本地goto”，立即退出内递归，但问题是，这条微优化是值得的麻烦。

更好的选择是将递归更改为循环。由于所有递归调用都处于“尾部位置”（是return的参数），因此可以用重置参数变量的代码替换它们。不幸的是，我不明白你的代码，所以我不能给你一个例子。

Answer 4

通过vector<string> words作为您的binsearch()函数的参考。目前，只要调用不需要的函数，它就会不断创建vector<string>的副本。此外，如果您想要更新该向量>，那么传递参考是最好的方法。

while循环之外应该有return声明。这将是最终的'回报'。

Answer 5

摆脱这种经典方法之一：重写它没有递归。

例如，使用while循环，然后一旦找到结果，就使用休息时间。你可以看看下面的代码（编译没有，只是从自己编写的代码快）

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

有跳出一个完整的调用堆栈的不优雅的或可移植的方式，它充其量相当危险的。此外，derecursified功能就会快得多：它并不需要推动的东西堆栈，并做了一个函数调用

编辑

• 添加缺少返回
• 关于演出：只是基准它。在这种特殊情况下，代码复杂性（对于读者而言）几乎相同，但取决于算法，它可能更加复杂（甚至不可能）。

Answer 6

您的代码有几个错误。对于初学者， 目前尚不清楚to和from是什么意思：它们包含在内，还是 排他。如果它们都包含在内（你的参数 对于递归调用似乎暗示），那么如何检测 的结尾。 test是什么意思？当你找不到这个单词时，你似乎将它用作 最终标准，但我看不出如何。

如果我写这个，我会使用一个简单的辅助类来保存 目标和单词列表（但你可以传播他们 下来明确），和一个包装功能，使客户端代码 没有按不必指定to和from参数。有 无需全局变量，或任何其他test。而 我会使用那些在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是比较大的，它将使上的表现非常 显著影响）

Answer 7

这是一个典型的运动中使用递归 - 当然，人们也可以做的事情非递归，但它的“让递归管理自己的簿记非常优雅”。对于那些膝盖反应是“迭代地进行”的人，我建议在合并排序或快速排序上做类似的练习。非常类似的递归结构，但是簿记在递归上下文中大大缓解。在现代的CPU上，递归代码 - 惊喜！ - 通常以更快或更快的速度运行以启动。

这是我的递归实现，使用OP的问题上下文。请注意，不需要单独测试中点元素：在比较谓词的C++“小于”范例的情况下（其中给出<，可以通过.not。（a.lt.b）.and ...推断相等性。不是。（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); 
} 

这里是上述的非递归版本，它纠正了发布的用户“布鲁斯”的示例代码的几个问题，并再次使用没有单独的中点值测试：

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

我做了上述两种实现的比较时间使用了一百万个准随机文本片段的向量，在MacOS上使用gcc 4.2构建的代码...递归版本运行速度慢了20％。不过，对于我的手动合并分类代码，递归速度更快。因人而异。