9.2.3. Стек и рекурсия

9.2.3. Стек и рекурсия

В качестве примера изоморфизма, существующего между стеком и рекурсией, рассмотрим классическую задачу о Ханойской башне.

По легенде где-то далеко на востоке существует старинный храм. Обитающие в нем монахи заняты решением единственной задачи: перемещением дисков с одного шеста на другой с соблюдением определенных правил. Первоначально на первом шесте было 64 диска. Когда все диски будут перемещены, настанет конец света.

Попутно разоблачим миф. Похоже, что на самом деле эту задачу впервые сформулировал французский математик Эдуард Люка в 1883 году, и никаких истоков в восточной культуре она не имеет. Сам Люка называл ее «Ханойской башней».

Так что если вас пугает конец света, можете успокоиться. Да и в любом случае для перемещения 64 дисков потребуется 2⁶⁴-1 ходов. Небольшой расчет на калькуляторе покажет, что монахи будут заняты своим делом несколько миллионов лет.

Однако вернемся к правилам игры. (Сформулируем их, хотя эту загадку знал уже самый первый студент самого первого факультета информатики.) Имеется шест, на который надето несколько дисков; назовем его исходным. Мы хотим переместить все диски на целевой шест, используя еще один вспомогательный шест как место промежуточного хранения. Проблема в том, что за один ход можно перемещать только один диск; при этом нельзя класть больший диск на меньший.

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

def towers(list)

 while !list.empty?

  n, src, dst, aux = list.pop

  if n == 1

   puts "Перемещаем диск с #{src} на #{dst}"

  else

   list.push [n-1, aux, dst, src]

   list.push [1, src, dst, aux]

   list.push [n-1, src, aux, dst]

  end

 end

end

list = []

list.push([3, "a", "c", "b"])

towers(list)

Вот что напечатает эта программа:

Перемещаем диск с а на с

Перемещаем диск с а на b

Перемещаем диск с с на b

Перемещаем диск с а на с

Перемещаем диск с b на а

Перемещаем диск с b на с

Перемещаем диск с а на с

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

def towers(n, src, dst, aux)

 if n==1

  puts "Перемещаем диск с #{src} на #{dst}"

 else

  towers(n-1, src, aux, dst)

  towers(1, src, dst, aux)

  towers(n-1, aux, dst, src)

 end

end

towers(3, "а", "с", "b")

Печатается точно такой же результат. Возможно, вам будет интересно знать, что «закомментарили» предложения, осуществляющие вывод, и сравнили время работы. Никому не говорите, но рекурсивное решение оказалось в два раза быстрее!