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

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 в качестве колышка "aux":

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
}