The Towers of Hanoi is a mathematical puzzle whose solution illustrates recursion. Learn about this problem and how to solve for three pegs which can hold stacks of disks of different diameters.
- [Instructor] Have you ever heard of the Towers of Hanoi?…You'll see this in many programing books,…as well as in many programing classes.…They'll use the story of the Towers of Hanoi…when you get to the section on recursion,…because it gives us a very concrete example…of a recursive process,…and we can visualize it in our head.…Let's take a look at the story.…Legend has it that when the world was created,…some high priests in the Temple of Bramha…were given three golden pegs.…On one of the pegs were placed 64 golden disks.…
The disks were all different sizes,…and they were stacked from smallest to largest.…The priests were given the task to move the 64 disks…from the given peg to one of the other two pegs,…but there's always a catch, right?…But there were rules.…Number one, they could only move one disk at a time.…Two, they could only move the topmost disk each time.…Three, the disk they just moved…must be moved to the top of another peg,…to the top of any disks on that peg.…
And four, no disk can be placed…on top of a smaller one.…
Programmers involved in mathematical computations, such as mathematical induction, are probably the biggest users of recursion. You probably know some of the most common recursive problems; finding the factorial of a number and the Fibonacci series are both examples of recursive processes. In this course, staff instructor and Java expert Peggy Fisher explores programming solutions involving both of these problems. She reviews the concept of recursion, discusses approaches to solving problems using recursion, and examines some recursive examples.
- Defining recursion
- Reviewing recursive examples
- Converting decimal to binary
- Printing a LinkedList
- Writing a power function