Как функция может выполнить действие после повторения?

Question

Я знаю, что рекурсия - это метод вызова функции внутри самой функции.но приведенный ниже код смущает меня тем, как он может выполнить часть cout после первой рекурсии:

(этот код решает головоломку Ханойской башни)

#include <iostream>
using namespace std;

void move_rings(int n, int src, int dest, int other); 

int main(void) 
{
    int rings;                      
    cout << "Number of Rings: ";   
    cin >> rings;
    move_rings(rings, 1, 3, 2);   

    system("PAUSE");
}

void move_rings(int rings, int source, int destination, int other)
{
     if (rings == 1)
     {
        cout << "Move from " << source << " to " << destination << endl;
     }
     else    
     {
         move_rings(rings - 1, source, other, destination);
         cout << "Move from " << source << " to " << destination << endl;
         move_rings(rings - 1, other, destination, source);  
     }
}

Как выКак видите, функция move_rings вызывает себя после оператора if.

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

?

cout << "Move from " << source << " to " << destination << endl; 

часть?

Вывод программы следующий:

Move from 1 to 3
Move from 1 to 2
Move from 3 to 2
Move from 1 to 3
Move from 2 to 1
Move from 2 to 3
Move from 1 to 3

Answer 1

Поначалу рекурсия может быть немного сложна для восприятия. Это «щелкнуло» для меня, когда я подумал об этом так: у вас есть базовый случай , что является условием, которое заставит рекурсивную функцию не вызывать себя больше, а затем у вас есть другая часть («else» в вашем коде), где функция будет по-прежнему вызываться. Условие "rings == 1" - ваш базовый случай.

Функция "move_rings" вызывается с меньшим аргументом каждый раз. При каждом последующем вызове переменная «rings» становится меньше (и, следовательно, «перемещается» ближе к базовому случаю), пока значение «rings == 1» не станет истинным, а затем функция перестанет вызывать себя.

Надеюсь, это поможет.

Answer 2

Поскольку каждый раз, когда вызывается move_rings(), его первый аргумент уменьшается. В конце концов, предполагая, что число колец бесконечно, функция будет вызываться только для одного кольца. Это условие завершения, которое приводит к возврату рекурсии.

Представьте это как бинарную древовидную структуру. Предполагая, что число узлов бесконечно, вы в конечном итоге достигнете конечного узла, за которым больше нет. Затем вы можете начать обход обратно по стеку вместе с другими путями кода, которые нашли конечные узлы.

Answer 3

Потому что при каждом вызове move_rings он передает параметр rings - 1.В конце переданный параметр будет 1 и rings == 1 будет истинным.

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

Answer 4

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

Во втором вызове функции rings будет иметь более низкое значение, потому что первый вызов прошелменьшее значение для этого параметра, чем его собственный.В конце концов, при одном из этих рекурсивных вызовов значение достигнет 1, а тест if в начале функции проверит true.Это позволяет избежать дальнейшей рекурсии, и эта функция возвращает.Непосредственно предыдущий вызов функции затем возобновляется с того места, где он был, как если бы он вызвал любую другую функцию.Он печатает, а затем делает еще один рекурсивный вызов, где происходит нечто подобное, и затем завершается.И так далее, «обратно».

Answer 5

Каждый раз, когда вы вызываете функцию move_rings, количество колец уменьшается на единицу. В конце концов, количество звонков будет 1. Этот код, однако, действительно мог бы создать бесконечный цикл, потому что он плохо написан. Количество колец никогда не проверяется, чтобы быть больше 1. Поэтому, если количество колец, введенных в основную функцию, меньше 1, условие прекращения рекурсии никогда не будет достигнуто.

Answer 6

В ветви else вызов выполняется с помощью rings - 1.Поскольку вы никогда не увеличиваете его, в конечном итоге rings будет 1, и ветвь if будет поражена.Поскольку в этой ветви не происходит рекурсии, метод завершается.

Answer 7

Каждый раз, когда функция повторяется, она получает количество звонков, уменьшенное на 1. В конце концов, все ветви достигают состояния rings==1 и завершаются.Вы можете представить это как двоичное дерево с его ветвями в состоянии else и его листьями в состоянии if.