Recurrence
From Wiki Notes @ WuJiewen.com, by Jiewen Wu
French Mathematician Edouard Lucas invented the Hanoi problem in 1883, which can be resolved recursively.
Hanoi: Let T(n) be the number of steps for move n-disk tower from one post to another. We first move the top n-1 disks, i.e.,T(n-1) steps; then move the remaining disk to another post, 1 step; finally move the n-1 disks onto that disk: T(n-1) steps. In total, T(n)=2*T(n-1)+1.
Now the Hanoi problem is a recurrence:
- T(1)=1;
- T(n)=2*T(n-1)+1;
To solve the recurrence, we have the following methods.
