递归与返回布尔值

发布于 2024-11-01 09:27:35 字数 720 浏览 1 评论 0原文

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 命令后尽快退出该函数，并将值相应地返回给主函数

谢谢

原文

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

i'm working on getting this binary search working. i need the overall function to return either "true" or "false". i understand how the recursion works up until either line 6 or 7 executes and the return command is invoked. i've done research, and it seems like there's no way to exit the function right there and it has to "unwind" itself. the tf global variable nonsense is so it won't execute that body again when it's unwinding...but i'm still not getting the results i want.

essentially, i just want to get out of the function ASAP after either the return true or return false command is invoked, and return the value to the main function accordingly

Thanks

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

帅的被狗咬 2024-11-08 09:27:35

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

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
}

I don't understand your binary search either, and using global variables in addition to recursion leads to programs which are very hard to understand. It's better to go back the call stack again and "unwind" it properly. Look at the following example (untested):

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
}

回复收藏 0 原文

一张白纸 2024-11-08 09:27:35

您可以使用 STL 的内置 binary_search，如下所示：

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

如果您这样做学习；有一些事情...

您不需要 while 循环。需要考虑三种情况：单词出现在 mid 之前，位于 mid< /code>，或在 mid 之后。这三种情况中的每一种都返回 - 因此甚至不可能到达循环体的末尾。
您在完全时使用test，并且您需要这个变量吗？
您应该仔细考虑仍然需要搜索的索引范围。 from 和 to 是包含的还是排除的？您需要精确且一致。
考虑正整数的除法向下舍入。无论它们具有什么值，确保递归调用调用较小的范围 - 以避免无限循环。这将有助于避免需要 test 变量（请参阅下面 David 的评论）。
使用全局变量不是一个好习惯；当然不是在其他纯函数中 - 我假设您这样做是为了调试目的？
to 和 from 可以有多大？在某些情况下，请注意 to+from 可能会超过 2^31-1。
在 C++ 中，通常使用迭代器来表达这些概念。当然，你不必这样做。
在 C++ 中，通常会尽可能通过 const & 传递大对象 - 这样，递归调用不需要复制整个向量。这对于正确性并不重要，但对于高效代码实际上非常重要。

You can use the STL's built-in binary_search as follows:

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

If you're doing this to learn; there are a few things...

You don't need a while loop. There are three cases to consider: the word comes before mid, at mid, or after mid. Each of these three cases returns - so it's impossible to even reach the end of the loop body.
You use test when exactly, and do you need this variable?
You should consider carefully exactly which range of indexes still needs to be searched. Are from and to inclusive or exclusive? You need to be precise and consistent.
Consider that division of positive integers rounds down. No matter what values they have, ensure that the recursive call calls a smaller range - to avoid infinite loops. This will help avoid the need for your test variable (see David's comment below).
It's not good practice to use global variables; certainly not in otherwise pure functions - I'm assuming you're doing this for debugging purposes?
How large can to and from be? In some cases, note that to+from may exceed 2^31-1.
It's typical in C++ to express these notions with iterators. You don't have to, of course.
It's typical in C++ to pass large objects by const & where possible - that way, the recursive call doesn't need to copy the entire vector. This is not important for correctness, but practically very important for efficient code.

回复收藏 0 原文

泅渡 2024-11-08 09:27:35

传递向量<字符串> Words 作为 binsearch() 函数中的参考。目前，每当调用不需要的函数时，它都会不断创建 vector 的副本。此外，将来如果您想更新该向量<>，那么通过引用传递是最好的方法。

while 循环之外应该有 return 语句。这将是最终的“回归”。

回复收藏 0 原文

森林散布 2024-11-08 09:27:35

摆脱这个问题的经典方法之一：不使用递归重写它。

例如，使用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;
}

没有优雅或可移植的方法来跳出完整的调用堆栈，它充其量是相当危险的。此外，去递归函数会更快：它不需要将东西推入堆栈并执行函数调用

编辑

缺失返回
添加有关性能的：只需对其进行基准测试即可。在这种特殊情况下，代码复杂性（对于人类读者而言）几乎相同，但根据算法的不同，它可能会复杂得多（甚至不可能）。

One of the classical way to get rid of this : rewrite it without recursion.

For example, use a while loop, then as soon as you find the result, use a break to go out. You can have a look at following code (not compiled, just written quickly from your own code)

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

There is no elegant or portable way to jump out of a full call stack, it's at best fairly risky. Moreover, the derecursified function will be much quicker : it does not need to push stuff on stack and do a a function call

Edit

added missing return
concerning performances : just benchmark it. In this particular case, code complexity (for the human reader) is almost the same, but depending on the algo, it can be much more complex (or even impossible).

回复收藏 0 原文

雾里花 2024-11-08 09:27:35

您的代码有几个问题。对于初学者来说，
目前尚不清楚 to 和 from 的含义：它们是包容性的，还是
独家的。如果它们都具有包容性（你的论点
递归调用似乎暗示），你如何检测
结尾。 test 是什么意思？您似乎正在使用它作为
当你找不到这个词时结束标准，但我不知道如何找到。

如果我写这个，我会使用一个简单的辅助类来保存
目标和单词列表（但你可以传播它们
显式向下），以及一个包装函数，以便客户端代码
不必指定 to 和 from 参数。有
不需要全局变量或任何额外的测试。和
我会使用 C++ 中惯用的半开区间： lower
包含边界，排除上限（因此 top == Bottom
指定了一个空范围，所以我已经完成但没有找到
element):

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比较大的话，就会造成很
对性能有重大影响。）

There are several things wrong with your code. For starters,
it's not clear what to and from mean: are they inclusive, or
exclusive. And if they're both inclusive (which your arguments
to the recursive calls seems to suggest), how do you detect the
end. And what does test mean? You seem to be using it as an
end criterion when you don't find the word, but I don't see how.

If I were writing this, I'd use a simple helper class to hold
the target and the word list (but you can just propagate them
down explicitly), and a wrapper function so that the client code
doesn't have to specify the to and from arguments. There's
no need for a global variable, or any additional test. And
I'd use the half open intervals that are idiomatic in C++: lower
bound inclusive, upper bound exclusive (so top == bottom
specifies an empty range, so I've finished without finding the
element):

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

Note that you can't do the comparison before testing that the
range isn't equal; it will cause an out of bounds access if all
of the elements are less than the target.

Also: I presume that you're doing this for pedagogical reasons.
Otherwise, you should just use the function in the standard
library. And I wouldn't normally use recursion here: there's
a straightforward iterative solution:

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

(Finally, you'll notice that I've converted your parameters to
references. It doesn't change anything in the logic of the
code, but if words is relatively large, it will make a very
significant impact on the performance.)

回复收藏 0 原文

无远思近则忧 2024-11-08 09:27:35

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

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

回复收藏 0 原文

夜灵血窟げ 2024-11-08 09:27:35

这是使用递归的经典练习 - 当然，人们也可以非递归地做事情，但是“让递归管理簿记”是非常优雅的。对于那些下意识反应是“迭代地执行”的人，我建议在合并排序或快速排序上进行类似的练习。非常相似的递归结构，但是在递归上下文中，簿记工作大大简化了。在现代 CPU 上，递归代码 - 令人惊讶！ - 通常运行速度一样快或更快，以启动。

这是我的递归实现，使用OP的问题上下文。请注意，无需单独测试中点元素：在比较谓词的 C++“小于”范式的上下文中（在给定 < 的情况下，可以通过 .not.(a.lt.b) .and 推断相等性）。 .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 万个准随机文本片段的向量对上述 2 个实现进行了比较计时，在 MacOS 上使用 gcc 4.2 构建的代码...递归版本运行速度慢约 20%。不过，对于我的手动合并排序代码，递归速度更快。 YMMV。

This is a classic exercise in using recursion - sure, one can also do things nonrecursively, but it's very elegant to "let the recursion manage one's bookkeeping." For those whose knee-jerk reaction is "do it iteratively", I suggest doing the analogous exercise on a merge-sort or quicksort. Very similar recursive structure, but the bookkeeping there is greatly eased in a recursive context. And on modern CPUs the recursive code - surprise! - often runs as fast or faster, to boot.

Here is my recursive implementation, using the OP's problem context. Note there is no need to separately test the midpoint element: Within the context of the C++ "less than" paradigm for comparison predicates (where given <, one can infer equality via .not.(a.lt.b) .and. .not.(b.lt.a) ), an extra test for equality of the midpoint makes little sense, although in the special case of the string class with its many-valued compare result, it may yield a modest speedup to add special handling for the 0-return result. My sample version assumes only < (in the sense that if one really only had <, one would slightly rearrange the divide-and-conquer conditional to use that), which generalizes more easily to numeric and user-defined data types:

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

And here is a non-recursive version of the above, which corrects several problems with the sample code posted by user 'Bruce' and again uses no separate midpoint-value test:

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

I did a comparative timing of the above 2 implementations using a vector of 1 million quasi-random text snippets, code built using gcc 4.2 on MacOS ... the recursive version runs ~20% slower. For my hand-rolled merge-sort code, though, recursive is faster. YMMV.

回复收藏 0 原文

~没有更多了~