Проблема в понимании потока рекурсии в Ханойских башнях - PullRequest
Новая
       54

Проблема в понимании потока рекурсии в Ханойских башнях

2 голосов
/ 12 апреля 2020

Я недавно изучаю структуры данных и алгоритм. Я получил просто рабочий код Ханойских башен. 

package linkedlist;

public class TowrerOfHanoi {

    public static void main(String[] args) {
        TowrerOfHanoi toh=new TowrerOfHanoi();
        toh.move(3,'A','C', 'B');
    }

    public void move(int numberOfDisc,char from,char to,char inter) {
        System.out.println(numberOfDisc);
        if(numberOfDisc==1) {
            System.out.println("Moving disc 1 from"+from
                    +"to"+to);
        }
        else {
            move(numberOfDisc-1,from,inter,to);
            System.out.println("Moving disc "+numberOfDisc+"from"+from
                    +"to"+to);  //confusion at this point
            move(numberOfDisc-1,inter,to,from);
        }

    }

}

Нет диска = 3 Вызвана функция перемещения и 

At first step: move(3,A,C,B) is passed and it goes to else block.
2nd step:Recursion is seen and  move(2,A,B,C) is called.
3rd step:Recursion is seen and  move(1,A,B,C) is called.

Так как noofdisc = 1 так, это идет первым, если блок, и я получил это: 

3
2
1
Moving disc 1 fromAtoC

Я ясно до этого момента и после этого я во время отладки я вижу noofdisk = 2 в консоли :

enter image description here

Поскольку наша последняя вызванная рекурсия была move (1, A, B, C) как Ноофдиск = 2? Я застреваю на этом этапе. Пожалуйста, помогите мне узнать, как я получаю noofdisk = 2 на этом этапе? Код работает нормально для Ханойских башен.

1 Ответ

1 голос
/ 12 апреля 2020

Когда я думаю о рекурсивных проблемах, я представляю каждый новый рекурсивный вызов как первый в стеке, где первый вызов обрабатывается первым. Когда перемещение вызывается с noof == 2, оно вычитает noof к 1 только для этого вызова и, следовательно, попадает в базовый случай, печатает «Moving dis c 1 fromAto C» и завершает вызов. В предыдущем вызове noof по-прежнему равняется 2, потому что он никогда не назначал noof в локальном экземпляре, а просто передавал его по убыванию.

...