title: analysis algorithm - recurrence equation (tower of hanoi)
body: <p>I saw this recursive algorithm to solve the Tower of Hanoi in wikipedia. Could someone explain to me how I get the recurrence equation of this algorithm?</p>
  <blockquote>
  <p>Recursive solution</p>
  <ul>
  <li>label the pegs A, B, C — these labels may move at different steps</li>
  <li>let n be the total number of discs</li>
  <li>number the discs from 1 (smallest, topmost) to n (largest, bottommost)</li>
  </ul>
  <p>To move n discs from peg A to peg C:</p>
  <ul>
  <li>move n−1 discs from A to B. This leaves disc n alone on peg A</li>
  <li>move disc n from A to C</li>
  <li>move n−1 discs from B to C so they sit on disc n</li>
  </ul>
  <p>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. This step, moving a single disc from peg A to peg B, is trivial.</p>
  </blockquote>