Towers of Hanoi is a recursive algorithm:

A method that is defined in terms of itself is called recursive. Recursion is a powerful design method that results in elegant and efficient algorithms.

A recursive algorithm always consists of a base case and a recursive call usually with smaller or simpler arguments. It is very important to ensure that recursion terminates (i.e. base case is reached for any imput)

Further examples of recursive algorithms include fibonacci, permutations as well as a number of other algorithms.

The Algorithm Pseudocode:

When current and final are the initial and final states, the algorithm is as follows:

    solve ( current, final )
    {
     let max be the number of disks
     let dest be the final place of max
     let disk = max
     repeat
          while disk > 0 do
             if disk is already on dest,
             or, moving it succeeds then
                  if disk = max then
                       decrement max by 1
                       if max = 0 then
                         return    // done
                       end if
                      let dest be the final place of max
                  end if
                          else
                  let dest be the alternative place between dest and
                  the current place of disk
             end if
              decrement disk by 1
          end while
          let p and q be the places different of dest
          let disk be the smaller of the disks on top of p and q
         let dest be the place between p and q with greater disk on top
         end repeat
    }

Solving recurrences, in other words, obtaining asymptotic "omega" or "O" bounds on the solution can be attained using the substitution method. Here, a bound can be estimated and then a mathematical induction is used to prove the estimate correct. The iteration method converts the recurrence into a summation and then relies on techniques for bounding summations to solve the recurrence. The master method provides bounds for recurrences of the form

T(n) = aT(n/b) + f(n),

where a >= 1, b > 1, and f(n) is a given function. It requires memorization of three cases, but once that is done, determining asymptotic bounds for many simple recurrences is easy.

The recursion tree

A variation of the substitution method which implements visual representation (Please see text book).