Kule Hanoja

Još jedan primer rekurzije je problem “kule Hanoja" koji je verovatno najpoznatiji rekurzivni problem u kompjuterskoj literaturi. Osnova problema su tri štapa A, B i C, koja su zabodena na ravnoj podlozi. Na jednom štapu, npr. na A, naslagano je n kolutova različitih prečnika poređanih po veličini tako da se najveći kolut nalazi na dnu, a najmanji na vrhu. Zadatak je preneti sve kolutove (jedan po jedan) s prvog na drugi štap. Postavlja se pitanje: Koliki je najmanji broj prenosa an potreban da se svih n kolutova prenese s prvog na drugi štap?

Pri prebacivanju kolutova treba poštovati sledeća pravila:

• U jednom potezu dozvoljeno je premestiti samo jedan kolut.
• Nije dozvoljeno staviti veći kolut preko manjeg.
• Svaki od štapova može se koristiti za privremeno smeštanje kolutova. Može se npr. koristiti treći štap C za privremeni smeštaj kolutova, ali uz poštovanje prethodna dva pravila.

> > DODATAK: Legenda o kuli Hanoja

Legenda kaže da je pre mnogo godina,negde u okolini grada Hanoj, živeo car koji je tražio novog dvorskog mudraca.Pošto je i sam bio mudar, želeo je da pronađe što boljeg mudraca, pa je rešio da uzme onoga koji da najbolje rešenje postavljenog problema (zagonetke): Dato je tri štapa i n diskova različitog prečnika. Svi diskovi su postavljeni na prvom štapu tako da se uvek manji disk nalazi iznad većeg. Potrebno je prebaciti sve diskove sa izvornog štapa na ciljni, premeštajući jedan po jedan disk, koristeći treći štap kao pomoćni, ali da se ni u jednom momentu disk većeg prečnika ne nađe na disku manjeg prečnika. Mnogi mudraci iz cele zemlje dolazili su pred cara sa raznim rešenjima, ali su rešenja bila ili nerazumljiva ili predugačka. „Mora da postoji jednostavniji način“, razmišljao je car. Jednog dana je pred cara stigao Buda, i rekao da je problem toliko jednostavan da se rešava sam od sebe. Svoje rešenje Buda je izložio na sledeći način: 1. Ako postoji samo jedan disk, pomeramo ga sa izvornog na ciljni štap, i to je toliko jednostavan posao da ga može uraditi svaka seoska luda. 2. Ako pak ima više od jednog diska postupak je sledeći: premestimo prvo n-1 diskova sa izvornog na pomoćni štap, koristeći ciljni kao pomoćni. Pošto je n-1 diskova na pomoćnom štapu, a najveći je i dalje ostao na izvornom, problem se svodi na tačku 1), tj. treba prebaciti taj jedan disk sa izvornog na ciljni štap. Potom treba n-1 diskova, sa pomoćnog štapa prebaciti na ciljni po istom postupku (sada koristeći izvorni štap kao pomoćni). Kada je Buda završio sa pričom, car ga je pitao kada će konačno reći svoje rešenje. Buda se samo nasmešio i otišao.

Iterativno rešenje ovog problema je veoma kompleksno, a rekurzivno prilično jednostavno. Ukoliko je n = 1, prebaciti disk sa polaznog na dolazni štap, inače: prebaciti (rekurzivno) n-1 diskova sa polaznog na pomoćni štap (korišćenjem dolaznog štapa kao pomoćnog), prebaciti najveći disk sa polaznog na dolazni štap i, konačno, prebaciti (rekurzivno) n-1 diskova sa pomoćnog na dolazni štap (korišćenjem polaznog štapa kao pomoćnog).

 				
#pomoćna funkcija koja štampa informaciju
def stampaj_korak(polazni, dolazni):   
    #sa kog štapa na koji štap se prebacio disk
    print ("Pomeri sa " + str(polazni) + " na " + str(dolazni)) 

#f-ja Kule za argumente uzima broj diskova i nazive štapova
def Kule(n, polazni, dolazni, pomocni):	
    if n == 1:	#bazni slučaj. Ako postoji samo jedan disk, izvršiti prebacivanje
        stampaj_korak(polazni, dolazni)
    else:		#rekurzivni korak
	#prvo se prebacuje n-1 diskova sa polaznog na pomoćni štap
        Kule(n-1, polazni, pomocni, dolazni)
	#najveći disk se prebaci sa polaznog na dolazni štap
        Kule(1, polazni, dolazni, pomocni)	 
	#na kraju, n-1 diskova se prebacuje sa pomoćnog na dolazni štap
        Kule(n-1, pomocni, dolazni, polazni)  

Kule(3, "A", "C", "B")

Program će ispisati sledeće:

 				
Pomeri sa A na C	
Pomeri sa A na B
Pomeri sa C na B
Pomeri sa A na C
Pomeri sa B na A
Pomeri sa B na C
Pomeri sa A na C