From: Brian Candler <b.candler@...>
Date: 2010-01-04T03:22:31+09:00
Subject: Re: Few clarifications on recursion

Phillip Gawlowski wrote:
>> :-) The important bit of recursion - and the part where recursion and
>> iteration differ - in programming languages is, that it needs a
>> _function (or method)_ which calls _itself_.
> 
> The actual difference is: recursion gives me headaches, iteration
> doesn't. ;P

:-)

But while this particular example is one which can easily be written 
either iteratively or recursively, there are many problems which are 
easy to solve recursively but more difficult to do iteratively.

Consider for example the classic "Towers of Hanoi" problem:

     -|-        |         |
    --|--       |         |
   ---|---      |         |
  ----|----     |         |
      A         B         C

Tower A is a stack of discs of decreasing size (I've shown 4; more often 
it's seen with 8 but I couldn't be bothered to drawn them :-)

The problem is to move all the discs from A to B. However the rules are:
- you can move only one disc at a time
- each disc after being lifted from one tower must be put down onto one 
of the other towers (A, B or C)
- you cannot put a larger disc on top of a smaller one

The recursive solution is simple: to move N discs from tower A to tower 
B, move N-1 discs from tower A to tower C, then move one disc from A to 
B, then move N-1 discs from tower C to tower B. The case of moving 0 
discs is trivial, and the rest just falls out.

This can be written in a handful of lines of code. You don't even need 
to maintain a data structure to record where the discs are(*). You'll 
find it needs 2^N moves to move a tower of height N.

(*) Although if you do, you can display the whole state at each point.
-- 
Posted via http://www.ruby-forum.com/.