Here is a recursive java algorithm program to compute the factorial of n!

Compile and run: TowersOfHanoi.java

Questions: 1) What is the "base case" and when does it get invoked? 2) How does the recursion solve the problem? 3) How does this recursive model resemble divide-and-conquer? 4) Why would using a "while loop" not be the best approach? 5) How can this estimate time to solve? 6) Would you say this is mathematically proven?

Towers of Hanoi Recursive Solution in Java Towers of Hanoi is a well known mathematical game/puzzle involving three pegs and a number of discs. The size of the discs are different and they are kept on the source peg with the smallest on the top and the biggest one on the bottom. The aim of the game is to move all the discs to a target peg with the same order using just a spare peg. The rules are, Only one disc can be moved at a time Each move consists of taking one disc from a peg and putting on top of another peg A disc cannot be placed over a smaller disc History of Towers of Hanoi French mathematician Edouard Lucas invented towers of Hanoi in 1883. One popular myth about towers of Hanoi suggests that there was a temple in India where priests worked on solving a 64 disc towers of Hanoi puzzle (known as tower of Brahma). Priests believed that when the last move of the puzzle is completed, world will end. Interestingly if the moves are made at the rate of one move per second, it will take more than 500 billion years to solve the puzzle! Solving Towers of Hanoi Using Recursion The number of steps required to move n discs from source page to target peg is (2 raised to n - 1). For example, it would take 7(2 raised to 3 - 1) steps to move 3 discs from source peg to target peg. This puzzle can be concisely solved using recursion. Let us look at the strategy of solving towers of Hanoi with just 2 discs. Move disc 1 from source peg to spare peg Move disc 2 from source peg to target peg Move disc 1 from spare peg to target peg For n number of discs we can generalize the above strategy as follows, Move n-1 discs from source peg to spare peg Move last disc from source peg to target peg Move n-1 discs from spare peg to target peg The first step of moving n-1 discs from source to spare peg is identical to our original problem, only difference being that the roles of the pegs change (spare peg becomes target and target peg becomes the spare peg)! This shows that we can recursively solve Towers of Hanoi. The termination condition for recursion will be n=1. The following Java program uses the above recursive strategy to solve Towers of Hanoi puzzle. The program will print the moves of the towers of Hanoi solution in the console. The heart of the program is the function solveTowersOfHanoi. It takes 4 parameters - number of discs to solve, source peg name, target peg name and spare peg name. It then immediately solves the problem if there is only 1 disc. If there is more than 1 disc, the function tries to move n - 1 discs from source peg to spare peg (note that the original peg in this case becomes

the spare peg!). This is recursive and hence all discs except the last one will be moved from source peg to spare peg. Then the final disc is moved from source peg to target peg. Finally n - 1 discs will be moved from spare peg to target peg in recursive mode. This completes the towers of Hanoi puzzle.