The Towers of Hanoi: Experiential Recursive Thinking

The Towers of Hanoi: Experiential Recursive Thinking
English


Instructors

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

Lesson Feedback

Introduction

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.

Instructor Biography

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 https://idss.mit.edu/staff/richard-larson/.

Additional Online Resources

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.

YouTube: Edouard Lucas' Tower of Hanoi Solved by Mitsubishi RV-1A Robot
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)

Wikipedia: Tower of Hanoi
This site is a comprehensive Wikipedia discussion of the Towers of Hanoi problem.

Cut the Knot: Tower of Hanoi
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.

SuperKids: Towers of Hanoi
This site, sponsored by Super Kids Educational Resources, provides an  interactive game for solving the Towers of Hanoi problem up to 7 disks.

Wolfram MathWorld: Tower of Hanoi
This site, sponsored by Wolfram MathWorld, provides a comprehensive discussion of and numerous references for the Towers of Hanoi problem.

YouTube: Hanoi towers 9 disks 511 moves
This site is a video demonstrating that the Towers of Hanoi problem for 9 disks can be done with a minimum of 511 moves.