The "towers of Hanoi" problem is stated like this. There are three
pegs labelled *a*, *b* and *c*. On peg *a* there
is a stack of *n* disks of increasing size, the largest at the
bottom, each with a hole in the middle to accomodate the peg. The
problem is to transfer the stack of disks to peg *c*, one disk at
a time, in such a way as to ensure that no disk is ever placed on top
of a smaller disk.

The problem is amenable to a divide and conquer strategy : "Move
the top *n - 1* disks from peg *a* to peg *b*, move the
remaining largest disk from peg *a* to peg *c* then, move
the *n - 1* disks on peg *b* to peg *c*."

```
let rec towers n from to_ spare =
if n > 0 then
begin
towers (n - 1) from spare to_;
Printf.printf
"Move the top disk from peg %c to peg %c\n" from to_;
towers (n - 1) spare to_ from
end
else
()
;;
```

For example, the
invocation ```
let () =
towers
3 'a' 'c' 'b'
```

will generate the recipie
Move the top disk from peg a to peg c Move the top disk from peg a to peg b Move the top disk from peg c to peg b Move the top disk from peg a to peg c Move the top disk from peg b to peg a Move the top disk from peg b to peg c Move the top disk from peg a to peg c

Let *T(n)* be the time complexity of ```
towers (x, y,
z)
```

, when the characteristic operation is the moving of a disk
from one peg to another. The time complexity of ```
towers(n - 1, x,
y z)
```

is *T(n - 1)* by definition and no further
investigation is needed. *T(0) = 0* because the test ```
n >
0
```

fails and no disks are moved. For larger `n`

, the
expression `towers (n - 1, from, spare, to_)`

is evaluated
with cost *T(n - 1)* followed by ```
Printf.printf "Move the top disk from peg %c to peg %c\n" from to_
```

with cost *1* and finally, ```
towers(n - 1, spare,
to_, from)
```

again with cost *T(n - 1)*.

Summing these contributions gives the recurrence relation *T(n) =
2T(n - 1) + 1* where *T(0) = 0*.

Repeated substituition can be used to arrive at a closed form
for *T(n)*, since, *T(n) = 2T(n - 1) + 1 = 2[2T(n - 2) + 1] + 1
= 2[2[2T(n - 3) +1] + 1] + 1 = 2 ^{3}T(n - 3) + 2^{2} +
2^{1} + 2^{0}* (provided

*n ≥*3), expanding the brackets in a way that elucidates the emerging pattern. If this substitution is repeated

*i*times then clearly the result is

*T(n) = 2*(

^{i}T(n - i) + 2^{i - 1}+ 2^{i - 2}+ ··· + 2^{0}*n ≥ i*). The largest possible value

*i*can take is

*n*and if

*i = n*then

*T(n - i) = T(0) = 0*and so we arrive at

*T(n) = 2*. This is the sum of a geometric series with the well known solution

^{n}0 + 2^{n - 1}+ ··· + 2^{0}*2*(use induction to establish that last result or more directly, just compute

^{n}- 1*2T(n) - T(n)*). And so, the time complexity (the number of disk moves needed) for

*n*disks is

*T(n) = 2*.

^{n}- 1
References:

Algorithms and Data Structures Design, Correctness, Analysis by Jeffrey Kingston, 2nd ed. 1998