Нужно объяснение рекурсивных вызовов в «Башнях Ханоя»

Question

Я понимаю концепцию рекурсии и то, как она складывается с каждым вызовом. Но я не могу объяснить, как работают рекурсивные вызовы и печатается, когда есть два вызова функции, разделенные командой printf. Может ли кто-нибудь объяснить мне, как работает этот рекурсивный вызов?

Я нашел пример игры «Башни Ханоя». В качестве примера рекурсии использовался Ut. Код:

#include <stdio.h> 

void transfer(int n, char from, char to, char temp); 

int main() 
{ 
    int n; 

    printf("how many disk"); 
    scanf("%d", &n); 
    printf("\n"); 
    transfer(n, 'L', 'R', 'C'); 
    return 0; 
} 

/* 
* n = number of disk, 
* from = origin, 
* to = destination, 
* temp = temporary storage 
*/ 
void transfer(int n, char from, char to, char temp) 
{ 
    if (n > 0) { 
     // Move n-1 disks from origin to temporary 
     transfer(n - 1, from, temp, to); 

     // Move n th disk from origin to destination 
     printf("move disk %d from %c to %c\n", n, from, to); 

     // Move n-1 disks from temporary to destination 
     transfer(n - 1, temp, to, from); 
    } 
} 

для n=3 дает выход как этот

 
move disk 1 from L to R // 
move disk 2 from L to C // 
move disk 1 from R to C // 
move disk 3 from L to R // 
move disk 1 form C to L // 
move disk 2 from C to R // 
move disk 1 from L to R // 

Answer 1

Вы могли бы думать о рекурсии в специальном варианте под названием «конец рекурсии»!? Башня алгоритма hanoi НЕ является конечной рекурсивной. Вместо этого он использует рекурсию еще дважды:

1. Переместить N-1 дисков выше диска N на временной стек (1-й передачи() вызова функции)
2. движение диска N в стек назначения (PRINTF)
3. переместить назад N-1 дисков из временного стека в пункт назначения bove disk N (вызов функции второй передачи())

Идея рекурсии функции передачи(): если она вызывается с n> 1 дисками для работы, он делегирует «работу» рекурсивным вызовам самого себя. Если вызывается с n == 1, он просто перемещает диск.

Вот модифицированная версия, которая должна сделать вещи яснее:

void transfer(int n, char from, char to, char temp) 
{ 
    if (n > 1) { 
     // Move n-1 disks from origin to temporary 
     transfer(n - 1, from, temp, to); 
    } 

    // Move n th disk from origin to destination 
    printf("move disk %d from %c to %c\n", n, from, to); 

    if (n > 1) { 
     // Move n-1 disks from temporary to destination 
     transfer(n - 1, temp, to, from); 
    } 
} 

Answer 2

я написал this post ответить именно такой вопрос, который я считаю, значительное количество начинающих сталкиваются.

Что происходит, когда у вас есть диски n.

Задача это движение п дисков от L к R через T, которая может быть разбита на:

1. Переместить верхние n-1 диски от L к T
2. Переместить нижний диск от L к R
3. Переместите диски n-1 с T по номеру R

Теперь обратите внимание, что шаги 1 и 3 сами являются проблемой Towers of Hanoi с дисками n-1 и различными полюсами источника и назначения. Шаг 1 представляет собой проблему для перемещения n-1 дисков с L до T по R, а на этапе 2 возникает проблема перемещения n-1 дисков с T до R через L.

Таким образом, проблема разбита на подзадачи, которые могут быть решены за один шаг, что представляет собой экземпляр проблемы с двумя дисками.

1. Переместить верхний диск с L в T
2. Перемещение нижнего диска из L в R
3. Переместить верхний диск с T в R

Чтобы получить лучшее понимание того, вы можете follow the link ,