Как работает рекурсивный алгоритм для Ханойских Башен?

Question

Это код из книги, в которой я объясняю рекурсию.Проблема в том, что я не понимаю, какие шаги предпринимала программа:

var hanoi = function(disc,src,aux,dst) {
    if (disc > 0) {
        hanoi(disc - 1,src,dst,aux);
        document.write("Move disc " + disc + " from " + src + " to " + dst + "<br />");
        hanoi(disc - 1,aux,src,dst);
    }
};

hanoi(3,"src","aux","dst");

Вот как вывод выглядит так:

Move disc 1 from src to dst
Move disc 2 from src to aux
Move disc 1 from dst to aux
Move disc 3 from src to dst
Move disc 1 from aux to src
Move disc 2 from aux to dst
Move disc 1 from src to dst

Может кто-нибудь разбить это шаг за шагом?Это было бы очень полезно для меня.

Answer 1

Вероятно, самое простое решение для Ханойских Башен работает следующим образом:

Чтобы переместить x диски из колышка A в колышек C, используя колышек B в качестве вспомогательного колышка:

1. Переместите x-1 диски из колышка A в колышек B, используя колышек C в качестве вспомогательного колышка.
2. Переместите x '-ый диск из колышка A в колышек C (дополнительный колышек не требуется,потому что вы перемещаете только один диск).
3. Переместите x-1 диски из колышка B в колышек C, используя колышек A в качестве вспомогательного колышка.

Обратите внимание, что по порядкудля перемещения дисков x необходимо переместить диски x-1.Вы можете просто использовать ту же функцию для перемещения этих дисков x-1 и просто переключать, какие колышки являются колышками source, dest и aux.Вот что делает Towers of Hanoi таким распространенным примером рекурсии, и именно такой шаблон вы должны увидеть в задаче, чтобы рекурсия работала для вас.Конечно, это не обязательно должен быть «переместить x-1 диски» ... это может быть что-то вроде «перечислить эту подпапку».Деревья (например, каталог с подпапками и т. Д.) - это еще одно место, где сияет рекурсия.Как и в случае других заданий, когда для выполнения задания над элементом вам, возможно, потребуется выполнить ту же работу с вложенными элементами.

Теперь, чтобы иметь полезную рекурсию, вам нужен «базовый случай»- состояние, при котором рекурсия остановится.Если вы этого не сделаете, код будет работать вечно (или, по крайней мере, пока он не исчерпает память или не переполнит стек вызовов).Базовый случай здесь возникает, когда x == 0 (так как перемещение 0 дисков означает, что вы ничего не делаете из-за if вокруг основной части функции).Это также может быть, когда x == 1, как тогда, вам не нужно повторяться, но дополнительные if перед каждым вызовом hanoi добавят немного шума (и главное преимущество рекурсивного решения - его простота).,В любом случае, когда x == 0, функция возвращается, ничего не делая.Функция, которая вызывала ее (у которой было x == 1), теперь продолжает делать свое дело - в этом случае, говоря «переместить диск 1 из src в dest», а затем снова вызывая функцию hanoi с переключенными аргументами.

Поток идет примерно так:

hanoi(3, src, aux, dest)
  hanoi(2, src, dest, aux)
    hanoi(1, src, aux, dest)
      hanoi(0, src, dest, aux)        // no op
      print "Move 1 from src to dest"
      hanoi(0, aux, src, dest)        // no op

    print "Move 2 from src to aux"

    hanoi(1, dest, src, aux)
      hanoi(0, dest, aux, src)        // no op
      print "move 1 from dest to aux"
      hanoi(0, src, dest, aux)        // no op

  print "move 3 from src to dest"

  hanoi(2, aux, src, dest)
    hanoi(1, aux, dest, src)
      hanoi(0, aux, src, dest)        // no op
      print "Move 1 from aux to src"
      hanoi(0, dest, aux, src)        // no op

    print "Move 2 from aux to dest"

    hanoi(1, src, aux, dest)
      hanoi(0, src, dest, aux)        // no op
      print "move 1 from src to dest"
      hanoi(0, aux, src, dest)        // no op

Answer 2

Я понял это. Если код разбит, он работает следующим образом:

var write = function(string) {
document.write(string);
}

var i = 0;

var hanoi = function(disc,src,aux,dst) {
    if (disc > 0) {
    hanoi(disc - 1,src,dst,aux);
    write("Move disc " + disc + " from " + src + " to " + dst + "<br />");
    hanoi(disc - 1,aux,src,dst);
    }
};

hanoi(3,"src","aux","dst");

/*
hanoi(3,"src","aux","dst");
    if (disc > 0) {
    hanoi(2,'src','dst','aux');
        if (disc > 0) {
        hanoi(1,'src','aux','dst');
            if (disc > 0) {
            hanoi(0,'src','dst','aux');
                END
            write("Move disc " + 1 + " from " + src + " to " + dst + "<br />");
            hanoi(0,'aux','src','dst');
                END
            }
        write("Move disc " + 2 + " from " + src + " to " + dst + "<br />");
        hanoi(1,'dst','src','aux');
            if (disc > 0) {
            hanoi(0,'src','dst','aux');
                END
            write("Move disc " + 1 + " from " + src + " to " + dst + "<br />");
            hanoi(0,'aux','src','dst');
                END
            }
        }
    write("Move disc " + 3 + " from " + src + " to " + dst + "<br />");
    hanoi(2,'aux','src','dst');
        if (disc > 0) {
        hanoi(1,'aux','dst','src');
            if (disc > 0) {
            hanoi(0,'src','dst','aux');
                END
            write("Move disc " + 1 + " from " + src + " to " + dst + "<br />");
            hanoi(0,'aux','src','dst');
                END
            }
        write("Move disc " + 2 + " from " + src + " to " + dst + "<br />");
        hanoi(1,'src','aux','dst');
            if (disc > 0) {
            hanoi(0,'src','dst','aux');
                END
            write("Move disc " + 1 + " from " + src + " to " + dst + "<br />");
            hanoi(0,'aux','src','dst');
                END
            }
        }
    }
*/

Самым запутанным в этом отношении была визуализация КОНЦА первого рекурсивного цикла. Только когда disc == 0, оператор с disc == 3, наконец, записывается.

Answer 3

function Hanoi(discs) {
  if(discs === 0) {
   return 0;
  }
 return 2 * Hanoi(discs - 1) + 1
}