![]() Take an example with 2 disks: Disk 1 on top of Disk 2 at peg A. Let’s try to solve a puzzle – Tower of Hanoi using recursion. Return x*factorial(x-1) // break into smaller problem(s)ĭetailed explanation to Recursion can be found – Here Tower of Hanoi algorithm explained Let’s take a simple example and try to understand those.įollowing is the pseudo code of finding the factorial of a given number X X using recursion. Recursion is useful in solving problems which can be broken down into smaller problems of the same kind.īut when it comes to solving problems using Recursion there are several things to be taken care of. ![]() So it’s like there is a function called d r e a m ( ) dream(), and we are just calling it in itself. Leonardo had a dream, in that dream he had another dream, in that dream he had yet another dream, and that goes on. It will be easier for those who have seen the movie Inception. When a function calls itself, it’s called Recursion. No disk can be placed on top of the smaller disk.īefore we proceed, let’s understand Recursion – What is Recursion?.The objective of the puzzle is to move the stack to another peg following these simple rules. Tower of Hanoi consists of three pegs or towers with n disks placed one over the other. It is good to understand how recursive solutions are arrived at and how parameters for this recursion are implemented. Tower of Hanoi is one of the classic problems to look at if you want to learn recursion. Hence this puzzle is often called Tower of Brahma puzzle. These priests acting on the prophecy, follow the immutable rule by Lord Brahma of moving these disk one at a time. According to a prophecy, when the last move of the puzzle is completed the world will end. These disks are continuously moved by priests in the temple. There is a story about an ancient temple in India (Some say it’s in Vietnam – hence the name Hanoi) has a large room with three towers surrounded by 64 golden disks. (previous) .Tower of Hanoi game is a puzzle invented by French mathematician Édouard Lucas in 1883. 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) .1997: David Wells: Curious and Interesting Numbers (2nd ed.) .Knuth and Oren Patashnik: Concrete Mathematics: A Foundation for Computer Science (2nd ed.): $\S 1.1$ 1986: David Wells: Curious and Interesting Numbers .The world may well have (figuratively) crumbled to dust long before that time. It is clear that steps $1$ and $3$ above each take $T_ - 1$ moves: $(1): \quad$ Move the tower of $n - 1$ disks from off the top of the $n$th disk onto another of the pegs $(2): \quad$ Move the $n$th disk to the destination peg $(3): \quad$ Move the tower of $n - 1$ disks from where it was put temporarily onto the top of the $n$th disk. ![]() Now, we note that in order to move a tower of $n$ disks, we need to do the following: Let $T_n$ be the number of moves needed to transfer $n$ disks from one peg to another. Variant $(1): \quad$ Only one disk can be moved at a time $(2): \quad$ No disk may be placed on a peg with a smaller disk beneath it $(3): \quad$ The disks must all be moved from the peg $1$ to peg $3$ $(4): \quad$ A move consists of transferring a disk from the peg $1$ to peg $2$, or back, or from peg $2$ to peg $3$, or back $(5): \quad$ No disk can cross over peg $2$ if it contains a smaller disk.įor a tower of $n$ disks, it takes $2^n - 1$ moves. How many moves are needed to move all the disks onto a different peg? $(1): \quad$ Only one disk can be moved at a time $(2): \quad$ No disk may be placed on a peg with a smaller disk beneath it. The object of the exercise is to move the disks onto a different peg, obeying the rules: There is a tower of $n$ disks, stacked in decreasing size on one of $3$ pegs.
0 Comments
Leave a Reply. |