Abhiraj Sinha

Tower of Hanoi, is a mathematical puzzle which consists of three towers (pegs) and more than one rings is as depicted − Tower Of Hanoi These rings are of different sizes and stacked upon in an ascending order, i.e. the smaller one sits over the larger one. There are other variations of the puzzle where the number of disks increase, but the tower count remains the same. Rules The mission is to move all the disks to some another tower without violating the sequence of arrangement. A few rules to be followed for Tower of Hanoi are − Only one disk can be moved among the towers at any given time. Only the "top" disk can be removed. No large disk can sit over a small disk. Following is an animated representation of solving a Tower of Hanoi puzzle with three disks. Tower Of Hanoi Tower of Hanoi puzzle with n disks can be solved in minimum 2n−1 steps. This presentation shows that a puzzle with 3 disks has taken 23 - 1 = 7 steps. Algorithm To write an algorithm for Tower of H...

What is Recursion? The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called as recursive function. Using recursive algorithm, certain problems can be solved quite easily. Examples of such problems are Towers of Hanoi (TOH), Inorder/Preorder/Postorder Tree Traversals, DFS of Graph, etc. A Mathematical Interpretation Let us consider a problem that a programmer have to determine the sum of first n natural numbers, there are several ways of doing that but the simplest approach is simply add the numbers starting from 1 to n. So the function simply looks like, approach(1) – Simply adding one by one f(n) = 1 + 2 + 3 +……..+ n but there is another mathematical approach of representing this, approach(2) – Recursive adding f(n) = 1 n=1 f(n) = n + f(n-1) n>1 There is a simple difference between the approach (1) and approach(2) and that is in approach(2) the function “ f( ) ” itself is being...