MIT Massachusetts Institute of Technology

The Towers of Hanoi: Experiential Recursive Thinking

Richard C. Larson
Mitsui Professor of Engineering Systems
Massachusetts Institute of Technology
Cambridge, Massachusetts USA

This lesson is about the Towers of Hanoi problem, a classic famous problem involving recursive thinking to reduce what appears to be a very large and difficult problem into a series of simpler ones.  The learning objective is for students to begin to understand recursive logic and thinking, relevant to computer scientists, mathematicians and engineers.   The lesson is experiential, in that each student will be working with her/his own Towers of Hanoi manipulative, inexpensively obtained.  There is no formal prerequisite, although some familiarity with set theory and functions is helpful.  The last three sections of the lesson involve some more formal concepts with recursive equations and proof by induction, so the students who work on those sections should probably be level 11 or 12 in a K-12 educational system.  The lesson has a Stop Point for 50-minute classes, followed by three more segments that may require a half to full additional class time.  So the teacher may use only those segments up to the Stop Point, or if two class sessions are to be devoted to the lesson, the entire set of segments.  Supplies are modest, and may be a set of coins or some washers from a hardware store to assemble small piles of disks in front of each student, each set of disks representing a Towers of Hanoi manipulative.  Or the students may assemble before the class a more complete Towers of Hanoi at home, as demonstrated in the video.  The classroom activities involve attempting to solve with hand and mind the Towers of Hanoi problem and discussing with fellow students patterns in the process and strategies for solution.

Dr. Larson's specialty is Operations Research, an interdisciplinary field that uses mathematics and the scientific method to improve decision-making in industry and government.  He has been involved with Technology-Enabled Education at MIT since 1995.  He is principal founder of MIT LINC, Learning International Networks Consortium and principal investigator of MIT BLOSSOMS.  His web site is http://esd.mit.edu/faculty_pages/larson/larson.htm.

This Power Point presentation, entitled Towers of Hanoi: Discovering the Invariant, was contributed to MIT BLOSSOMS By Dr. Fakhar Lodhi, Professor at the National University of Computer and Emerging Technologies in Lahore, Pakistan. Watch as slide show.

This site presents a Mitsubishi RV-1A Robot solving the Towers of Hanoi problem. (a brief segment of this is shown in the BLOSSOMS video lesson)
http://www.youtube.com/watch?v=8MiwUqZrnK8 

This site is a comprehensive Wikipedia discussion of the Towers of Hanoi problem.
Wikipedia:  http://en.wikipedia.org/wiki/Tower_of_Hanoi

This site, sponsored by Math Around the World, provides printable materials that can be used by students to work on the Towers of Hanoi problem.
http://www.lawrencehallofscience.org/java/tower/towerprintout.html

This site, hosted by Cut the Knot, provides an interactive applet game enabling students to solve the Towers of Hanoi problem with a varying numbers of disks, in a fast or slow manner.
http://www.cut-the-knot.org/recurrence/hanoi.shtml

This site, sponsored by Super Kids Educational Resources, provides an  interactive game for solving the Towers of Hanoi problem up to 7 disks.
http://www.superkids.com/aweb/tools/logic/towers/

This site, sponsored by Wolfram MathWorld, provides a comprehensive discussion of and numerous references for the Towers of Hanoi problem.
http://mathworld.wolfram.com/TowerofHanoi.html

This site is a video demonstrating that the Towers of Hanoi problem for 9 disks can be done with a minimum of 511 moves.
http://www.youtube.com/watch?v=N9m_l4cqcTY

Good Efforts..

Anonymous
July 28, 2012 at 7:36 am

Good Efforts..

Thanks for the correction. We

Anonymous
March 4, 2012 at 12:13 pm

Thanks for the correction. We will do the video correction asap.

-- Dick Larson

Error at 27:13 steps to solve

Anonymous
March 3, 2012 at 10:13 am

Error at 27:13 steps to solve the 3 disk problem are incorrect.

Great efforts, Dick I wish

seddiq
February 28, 2012 at 7:09 am

Great efforts, Dick
I wish more success to you

Add A Comment
By submitting this form, you accept the Mollom privacy policy.

This Lesson is in the following clusters: Computer Programming, Mathematical Induction

Good Efforts..

Anonymous
July 28, 2012 at 7:36 am

Good Efforts..

Thanks for the correction. We

Anonymous
March 4, 2012 at 12:13 pm

Thanks for the correction. We will do the video correction asap.

-- Dick Larson

Error at 27:13 steps to solve

Anonymous
March 3, 2012 at 10:13 am

Error at 27:13 steps to solve the 3 disk problem are incorrect.

Great efforts, Dick I wish

seddiq
February 28, 2012 at 7:09 am

Great efforts, Dick
I wish more success to you