Понимание кода C ++: Ханойская башня с использованием рекурсии

Question

я изучаю рекурсию в c ++, но был озадачен следующим кодом c ++, используемым для решения проблемы Tower of Hanoi.

void Hanoi(int m, string start, string middle, string end){
    cout << "m is equal to: " << m << endl;
    if(m == 1){
        cout << "Move Disc " << " from " << start << "  to " << end << endl;
    }
    else{
        Hanoi(m-1,start,end,middle);
        cout << "Move disc " << m << " from " << start << " to " << end << endl;
        Hanoi(m-1,middle,start,end);
    }
}
int main(){
    int discs = 3;
    Hanoi(discs, "start","middle","end");

} 

вывод кода следующий:

m is equal to: 3
m is equal to: 2
m is equal to: 1
Move Disc  from start  to end
Move disc 2 from start to middle
m is equal to: 1
Move Disc  from end  to middle
Move disc 3 from start to end
m is equal to: 2
m is equal to: 1
Move Disc  from middle  to start
Move disc 2 from middle to end
m is equal to: 1
Move Disc  from start  to end

Моя общая проблема - я не понимаю, как работает рекурсия.почему я должен перейти к 1, прежде чем он выполнит оператор "если"?как м вернуться к 2?

Answer 1

Ваша цель - переместить все диски в другое место.

• Чтобы решить головоломку, вам необходимо переместить башню из положения 1 в положение 2.

• Для этого вам необходимо переместитьсясамый большой диск из положения 1 в положение 2.

• Для этого положение 2 должно быть пустым, а все остальные диски должны быть в положении 3 (как башня размером m-1).

• Итак, вам нужно решить головоломку для размера m-1 (переместить башню размера m-1 из положения 1 в 3).Это первый рекурсивный вызов.

• Теперь вы можете переместить самый большой диск из положения 1 в положение 2. Это выход между вызовами рекурсивной функции.

• Теперь вам нужно переместить башню размера m-1 из положения 3 в положение 2.

• Так что вам нужно снова решить головоломку для размера m-1 (переместите башню размером м-1 из положения 3 в 2).Это второй рекурсивный вызов функции.

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

Answer 2

Этот след должен помочь вам, если нет, то вы всегда можете найти больше следов, прибегая к помощи "Следа программы рекурсии Ханойской башни"

Вы также можете найтикак работает алгоритм на https://javabypatel.blogspot.com/2015/12/tower-of-hanoi.html

Answer 3

Давайте начнем с первой части вывода: m is equal to: 3 m is equal to: 2 m is equal to: 1

Функция Hanoi сначала вызывается так: Hanoi(3).
Поскольку m != 1 в этом случае, мы будемпозвоните Hanoi(m-1) еще раз.Это даст результат выше.Сейчас мы на 3 уровня в глубине этой функции.

Начиная с m == 1, мы теперь увидим этот вывод: Move Disc from start to end.

Теперь мы выходим из самой глубокой функции и возвращаемся к уровню 2 нашего стека вызовов функций.Теперь мы выводим: Move disc 2 from start to middle.

Answer 4

Если вы напечатаете его в виде дерева, вы получите что-то вроде этого:

main
  |--> hanoi(3, ...)
  |      |
  |      |--> hanoi(2, ...)
  |      |     |
  |      |     |--> hanoi(1, ...)
  |      |     |--> hanoi(1, ...)
  |      |<----|
  |      |--> hanoi(2, ...)
  |      |     |
  |      |     |--> hanoi(1, ...)
  |      |     |--> hanoi(1, ...)
  |      |<----|
  |<-----|
  |

Для каждого вызова hanoi(m, ...) он будет удерживать вызов hanoi (m - 1, ...) дважды, если только не m == 1. Во время первого вызова он снова вызовет вызов hanoi (m - 1, ...) ... до тех пор, пока m не станет равным 1.

Поэтому, возвращаясь назад, когда m равно 2, он будет вызывать Ханой (1,...) два раза подряд:

   hanoi(2, ...)
      hanoi(1, ...)
      hanoi(1, ...)

Когда m равно 3, два раза подряд будет вызываться Ханой (2, ...), следовательно:

hanoi(3, ...)
   hanoi(2, ...)
      hanoi(1, ...)
      hanoi(1, ...)
   hanoi(2, ...)
      hanoi(1, ...)
      hanoi(1, ...)