рекурсия и возврат логических значений

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 такова, что он не будет выполнять это тело снова, когда он раскручивается ... но я все еще не получаю желаемых результатов.

по сути, я просто хочу выйти из функции как можно скорее после того, как будет выполнена команда return true или return false, и вернуть значение основной функции соответственно

Спасибо

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 следующим образом:

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

Если вы делаете это для обучения;Есть несколько вещей ...

• Вам не нужен цикл while. Есть три случая, которые следует рассмотреть: слово стоит перед mid, в mid или после mid.Каждый из этих трех случаев return s - поэтому невозможно даже достичь конца тела цикла.
• Вы используете test, когда точно , и нужна ли вам эта переменная?
• Вы должны тщательно точно определить, какой диапазон индексов еще нужно найти. Являются ли from и to включающими или исключающими? Вы должны быть точными и последовательными.
• Учтите, что деление натуральных чисел округляется в меньшую сторону.Независимо от того, какие значения они имеют, гарантирует, что рекурсивный вызов вызывает меньший диапазон - чтобы избежать бесконечных циклов.Это поможет избежать необходимости в вашей переменной test (см. Комментарий Дэвида ниже).
• Не рекомендуется использовать глобальные переменные ;конечно, не в чистых функциях - я предполагаю, что вы делаете это для целей отладки?
• Насколько большими могут быть to и from? В некоторых случаях обратите внимание, чтоto+from может превышать 2^31-1.
• Обычно в C ++ выражать эти понятия с помощью итераторов.Конечно, вам не нужно.
• В C ++ обычно передаются большие объекты по const &, где это возможно - таким образом, рекурсивному вызову не нужно копировать весь вектор.Это не важно для правильности, но практически очень важно для эффективного кода.

Answer 3

В вашем коде есть несколько ошибок. Для начинающих, непонятно, что означают to и from: включительно или эксклюзив. И если они оба включительно (что ваши аргументы на рекурсивные вызовы, кажется, предлагает), как вы обнаруживаете конец. А что значит test? Вы, кажется, используете это как критерий конца, когда вы не можете найти слово, но я не понимаю, как.

Если бы я писал это, я бы использовал простой вспомогательный класс для хранения цель и список слов (но вы можете просто распространять их явно), и функция-обертка, чтобы клиентский код не нужно указывать аргументы to и from. Там в нет необходимости в глобальной переменной или каких-либо дополнительных test. А также Я бы использовал полуоткрытые интервалы, которые являются идиоматическими в C ++: ниже переплет включительно, верхний переплет эксклюзив (так top == bottom указывает пустой диапазон, поэтому я закончил, не найдя элемент): * 1 010 *

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 4

Один из классических способов избавиться от этого: переписать его без рекурсии.

Например, используйте цикл 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;
}

Не существует элегантного или портативного способа выпрыгнуть из полного стека вызовов, в лучшем случае это довольно рискованно. Кроме того, функция с отменой рекурсии будет намного быстрее: ей не нужно помещать вещи в стек и выполнять вызов функции

Редактировать

• добавлено пропущенное возвращение
• относительно выступлений: просто сравните это. В этом конкретном случае сложность кода (для читателя-человека) практически одинакова, но в зависимости от алгоритма она может быть гораздо более сложной (или даже невозможной).

Answer 5

Pass vector<string> words как ссылка в вашей функции binsearch(). В настоящее время он продолжает создавать копии vector<string> всякий раз, когда вызывается функция, которая не нужна. Более того, в будущем, если вы захотите обновить этот вектор <>, лучше всего будет передать по ссылке.

Должен быть оператор return вне цикла while. Это будет окончательное «возвращение».

Answer 6

Это классическое упражнение по использованию рекурсии - конечно, можно делать что-то нерекурсивно, но очень элегантно «позволить рекурсии управлять своей бухгалтерией». Для тех, чья реакция коленного рефлекса - «делай это итеративно», я предлагаю выполнить аналогичное упражнение для сортировки слиянием или быстрой сортировки. Очень похожая рекурсивная структура, но бухгалтерия там значительно упрощена в рекурсивном контексте. А на современных процессорах рекурсивный код - сюрприз! - часто запускается так же быстро или быстро, чтобы загрузить.

Вот моя рекурсивная реализация, использующая проблемный контекст ОП. Обратите внимание, что нет необходимости отдельно проверять элемент средней точки: в контексте C ++ парадигмы «меньше чем» для предикатов сравнения (где дано <, можно вывести равенство через .not. (A.lt.b) .and.. нет. (b.lt.a)), дополнительный тест на равенство средней точки не имеет большого смысла, хотя в особом случае класса string с его многозначным результатом сравнения он может привести к небольшому ускорению для добавления специальной обработки для 0-возврата результата. Моя примерная версия предполагает только <(в том смысле, что если бы у кого-то действительно было <, то можно было бы немного переставить условное условие «разделяй и властвуй», чтобы использовать его), что упрощает обобщение для числовых и пользовательских типов данных: </p>

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

Я выполнил сравнительную синхронизацию двух вышеописанных реализаций, используя вектор из 1 миллиона квазислучайных фрагментов текста, код, созданный с использованием gcc 4.2 для MacOS ... рекурсивная версия работает примерно на 20% медленнее. Однако для моего кода с сортировкой слиянием, выполненного вручную, рекурсивна быстрее. YMMV.

Answer 7

Вы можете использовать longjmp, иначе "нелокальный goto", для немедленного выхода из внутренней рекурсии, но вопрос в том, стоит ли эта микрооптимизация. 1005 *

Лучшим вариантом является преобразование рекурсии в цикл. Поскольку все рекурсивные вызовы находятся «в хвостовой позиции» (являются аргументом return), вы можете заменить их кодом, который сбрасывает переменные параметра. К сожалению, я не понимаю ваш код, поэтому не могу привести пример.