Можно ли преждевременно покинуть рекурсию?

Question

Моя текущая рекурсивная функция работает до некоторой степени, но затем разрушается, когда возвращается в стек.

void Graph::findPath( Room * curRoom )
{
if( curRoom -> myNumber == 0 )
{
    cout << "Outside.\n";
    //Escape the recursion!
}
else
{
    curRoom -> visited = true;

    if( curRoom -> North -> visited == false )
    {   

        escapePath[ _index ] = "North";
        cout << "_index: " << _index << "\n";
        ++_index;

        findPath( curRoom -> North );

        cout << "_index: " << _index << "\n";
        escapePath[ _index ] = "";
        --_index;
    }

    if( curRoom -> East -> visited == false )
    {   
        escapePath[ _index ] = "East";
        cout << "_index: " << _index << "\n";
        ++_index;

        findPath( curRoom -> East );

        cout << "_index: " << _index << "\n";
        escapePath[ _index ] = "";
        --_index;
    }

    if( curRoom -> South -> visited == false )
    {   
        escapePath[ _index ] = "South";
        cout << "_index: " << _index << "\n";
        ++_index;

        findPath( curRoom -> South );

        cout << "_index: " << _index << "\n";
        escapePath[ _index ] = "";
        --_index;
    }

    if( curRoom -> West -> visited == false )
    {   
        escapePath[ _index ] = "West";
        cout << "_index: " << _index << "\n";
        ++_index;

        findPath( curRoom -> West );

        cout << "_index: " << _index << "\n";
        escapePath[ _index ] = "";
        --_index;
    }
}
}

Чтобы сэкономить ваше чтение, идея состоит в том, что базовый случай находит 0. В противном случае он пробует четыре разных кардинальных направления, то есть номер с другим номером. Каждый раз, когда он делает ход, он добавляет ход, который он сделал, во внешний массив, и каждый раз, когда он возвращается, он удаляет этот шаг из стека.

Моя проблема в том, что он сохраняет правильный путь, когда находит 0, но удаляет его при обратном копировании.

Есть ли способ избежать этого, например, перерыв.

Нет gotos или исключений

Answer 1

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

bool Graph::findPath( Room * curRoom )
{
    if( curRoom -> myNumber == 0 )
    {
        cout << "Outside.\n";
        //Escape the recursion!
        return true;
    }
    // ...
    if (findPath( curRoom -> North ))
        return true;
    // ...
    return false;
}

Answer 2

В

//Escape the recursion!

Я думаю, вы можете просто сохранить копию «ответа» в поле за пределами вашей рекурсии.Если функция уже изменяет поля, уже находящиеся вне рекурсии, возможно, сделайте это частной вспомогательной функцией, которая содержит дополнительный логический параметр, который указывает, хотите ли вы выйти.Публичная функция может просто вызывать эту функцию, чтобы абстрагироваться от наличия в параметрах флага, подобного этому.

Что-то вроде:

void Graph::findPath( Room * curRoom, bool done )

---

//Escape the recursion!
done = true;

---

findPath( curRoom -> North );

if (done) // new line here
    return;

cout << "_index: " << _index << "\n";
escapePath[ _index ] = "";
--_index;

Answer 3

Возможно longjmp и setjmp: http://www.cplusplus.com/reference/clibrary/csetjmp/. Но я не думаю, что это хорошая идея использовать longjmp и setjmp в C ++.

Лучше установить какое-то специальное возвращаемое значение, которое при обнаружении на некоторой глубине сразу же вернется, как в C.

Или глобальный флаг, указывающий состояние рекурсии, если true, мы можем сделать, иначе рекурсия должна вернуться.

Answer 4

исключения (или C longjmp) - это способ выхода из рекурсии. Вы также можете иметь флаг static boolean leaveme; и начать свою работу с if (leaveme) return; и т. Д.

Но longjmp плохо работает с деструкторами значений в локальных фреймах (в то время как исключения работают).