< ----Recursive c program for towers of Hanoi problem ---->

key to solving this puzzle is to recognize that it can be solved by breaking the problem down into a collection of smaller problems and further breaking those problems down into even smaller problems hence making it a typical best suited problem for recursion .

example:   the pegs are  A, B, C and n is the total number of discs number the discs from 1 the largest of the discs and 5(variable DISCS) the smallest.
move n−1 discs from A to B. This leaves disc n alone on peg A
move disc n from A to C
move n−1 discs from B to C so they sit on disc n
The above is a recursive algorithm, to carry out steps 1 and 3, apply the same algorithm again for n−1. The entire procedure is a finite number of steps, since at some point the algorithm will be required for n = 1.

here is the program/code  in c

1. #include<stdio.h>
2. #define P(x) printf("%d\n",x);
3. #define Ps(x) printf("\n\n%s=\n",x)
4. #define DISCS 10
5. struct stack1
6. {int a[10],top;
7. };
8. typedef struct stack1 stack;
9.  
10. initialize(stack *s1,stack *s2,stack *s3)
11. {
12.     s1->top=s2->top=s3->top=-1;
13. }
14. int push(stack *s,int x)
15. {
16.     return(s->top<=(DISCS-2)?s->a[++s->top]=x,1:0);
17. }
18. int pop(stack *s)
19. {
20.     return(s->top==-1?-999:s->a[s->top--]);
21. }
22. move(stack *s1,stack *s2)
23. {
24.     int x=pop(s1);
25.     push(s2,x);
26. }
27. printstack(stack *s3)
28. {   int to=s3->top,d=pop(s3);
29.     for(;!(d==-999);d=pop(s3))P(d);
30.     s3->top=to;
31. }
32. tower_of_hanoi(stack *t1,stack *t2,stack *t3,int pgs)
33. {    //you can print the stack here also, after each function call
34.     if(pgs>0){
35.      tower_of_hanoi(t1,t3,t2,pgs-1);
36.     move(t1,t2);
37.      tower_of_hanoi(t3,t2,t1,pgs-1);
38.              }
39. }
40. main()
41. {
42.      stack s1,s2,s3;
43.      initialize(&s1,&s2,&s3);
44.      int d=1;//pegs 1  being the largest and DISCS the smallest
45.      for(;push(&s1,d++););
46.      Ps("orig/first stack");
47.      printstack(&s1);
48.      tower_of_hanoi(&s1,&s2,&s3,DISCS);
49.      Ps("first stack");
50.      printstack(&s1);
51.      Ps("second stack");
52.      printstack(&s2);
53.      Ps("third stack");
54.      printstack(&s3);
55. }

NOTE : the number of discs is stored in predefined in DISCS , which can be changed to any value . But for every ring added the algorithm will take twice the time and memory for computation hence the following code may fail for values above 10 for DISCS