Posted by: aphr | June 11, 2009

Recursion – solving the smaller case first.

When solving a problem that involves a certain number n of similar objects, it sometimes helps to solve the same problem for (n-1) objects. If one sees an easy way to compute the solution for all n objects from a solution for (n-1) objects, one can often calculate the (n-1)-solution by solving (n-2) first – and start building a solution by solving with 1 object at first.

Example: In the Tower of Hanoi game the player has to move a stack of disks of different sizes to another rod, obeying the following rules:

  • Only one disk may be moved at a time.
  • Each move consists of taking the upper disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.
  • No disk may be placed on top of a smaller disk.

Tower of Hanoi
It is easy to move a tower of size 5 from rod 1 to rod 3, as long as you know how to move a tower of size 4. Simply move 4 pieces to rod 2, then move the largest piece from rod 1 to rod 3 and finally move 4 pieces from rod 2 to rod 3. We have reduced the problem to n-1 pieces. How do we move n-1 pieces to rod 2? well, we simply move n-2 pieces to rod 3 first…
In this manner we reduce the problem to the act of moving a single piece at a time.

Solving problems recursively – by reducing them to smaller problems time and again – is not always the fastest way to get a result and often involves remembering a lot of smaller solutions or writing them down. Recursive solutions are however elegant, easy to communicate and quick to code as a computer program.

Riddle: The thirteen pirates on the “Black Seagull” have a clear chain of command with captain Blackbeard being number one and lazy Pete being number 13 in the chain. Using an old map they find a treasure of 1000 gold pieces. They now divide the money in the following way:
Blackbeard, being the first in command, proposes a distribution. All pirates then individually and selfishly decide whether they accept the split or not. If more than 50% of the pirates do not accept the split, they throw the first in command over boards. The command goes to the next pirate, who proposes a split, etc. It is safe to assume that the pirates are revenue-maximizing economic agents who are capable of thinking the situation through to the end.
If you were captain Blackbeard, which split do you propose to ensure that you (1) do not get eaten by sharks and (2) keep the largest part of the money at the same time?


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s


%d bloggers like this: