why do we consider n-1 disks as the top n-1 disks . why dont we think as bottom n-1 disks. for example , in case of reversing a stack using 1 extra stack we removed the first element and reverse n-1 elements . similarly , why dont we think here also that we are picking up the top most disk and transferring the bottom n-1 disks to the other tower ? why doesnt this approach work ?
Towers of hanoi
Hey Shubham
If you deal with recursive problems, remember that you need to solve only smaller problem and let recursion deal with the larger subset.
In tower of hanoi,
Consider n disks, we give n-1 disks to recursion (either give first n-1 disks or last n-1 disks)
As a tradition we chose last disk for ourselves and give first n-1 disks to recursion as we can easily track the last disk which will always be the nth disk.
You can however, deal with first disk and pass bottom n-1 disks to recursion but then you will need to track which one is the first disk while printing, 1st disk,2nd disk and so on…That is why we avoid complicating the things and use the former approach to make our lives easier and you will find that approach only almost everywhere!
I hope I got your question in the right way?
Do let me know if you have any further doubts!!
As you said , we can consider the top most disk for ourself and give the bottom n-1 disks to recursion .For this approach , the recurrence relation becomes T(n)= T(n-1) +1 , since recursion can just transfer bottom n-1 disks to the other tower , can now we have to just put the top most disk at the top of stack which takes 1 operation . However the standard solution gives the relation T(n)= 2*T(n-1) +1.
Why is there difference between the two ?
Yess you are right with the recurrence relation and obviously there will be a difference as the number of recursive calls we are making in the approaches are different.
Now suppose the method used traditionally changes to:
recur(n-1,src,dest,aux)
print(n,src,aux)
recur(n-1,dest,src,aux)
print(n,aux,dest)
recur(n-1,src,dest,aux)
Now its recurrence is T(n)=3T(n-1)+1
Lets modify the approach we are working on now as well:
//working on starting disc instead of last
print(start,src,dest)
recur(n-1,src,aux,dest)
print(start,dest,src)
recur(n-1,aux,dest,src)
print(start,src,dest,aux)
Now recurrence relation becomes T(n)=2T(n-1)+1
So in conclusion, it totally depends on the number of recursive calls which obviously are up to you!
Hope I was able to make myself clear? Let me know for further doubts…
Hey Shubham
If your doubt is resolved then you can mark it resolved else let me know if u have anything further to discuss 
Hii Shubham I am marking your doubt as resolved as you have inactive for some time …But you can reopen it any time.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.