Πύργοι του Hanoi

Παράδειγμα Αλγορίθμου με ανάδρομη δράση

Αναδρομικός αλγόριθμος ονομάζεται αυτός που λύνει ένα πρόβλημα λύνοντας ένα ή περισσότερα μικρότερα στιγμιότυπα του ίδιου προβλήματος

Πρόκειται για έναν θρύλο γνωστός και ως Πύργοι του Brahma ή Πύργοι του Lucas.
Σύμφωνα με τον θρύλο στο ναό Hindu, στις αρχές του έτους δινόταν για λόγους πειθαρχίας στους μοναχούς μια δοκιμασία :
Υπήρχαν τρεις στύλοι, στον έναν ήταν τοποθετημένοι κατά φθίνουσα σειρά 64 δίσκοι. Οι δίσκοι έπρεπε να μετακινηθούν σε άλλον στύλο, τηρώντας τους εξής κανόνες:

• ένας δίσκος δεν κάνει να τοποθετηθεί πάνω σε μικρότερο.
• μετακινούμαι πάντα μόνο έναν δίσκο.

Λέγονταν μάλιστα πως, εάν μετακινηθούν όλοι οι δίκοι, τότε θα έρθει το τέλος του κόσμου.

Τα μαθηματικά πίσω από τον θρύλο 
Παρατηρούμε ότι  για τη μεταφορά :

• 3  δίσκων  απαιτούνται  7 κινήσεις    δηλ    2³- 1   κινήσεις.
• 4  δίσκων  απαιτούνται  15 κινήσεις  δηλ    2⁴- 1   κινήσεις.
• 5  δίσκων  απαιτούνται  31 κινήσεις  δηλ    2⁵- 1   κινήσεις.
• 6  δίσκων  απαιτούνται  63 κινήσεις   δηλ    2⁶- 1   κινήσεις.

άρα  για   τη μεταφορά  64  δίσκων  απαιτούνται   2⁶⁴-1   κινήσεις