Xref: utzoo comp.edu:3618 uw.general:1838
Path: utzoo!attcan!uunet!ogicse!milton!wiml
From: wiml@milton.u.washington.edu (William Lewis)
Newsgroups: comp.edu,uw.general
Subject: Re: Recursion?
Message-ID: <8699@milton.u.washington.edu>
Date: 6 Oct 90 20:58:14 GMT
References: <1990Oct5.101354.593@contact.uucp> <1990Oct05.221120.25060@xenitec.on.ca>
Distribution: na
Organization: University of Washington, Seattle
Lines: 32

In article <1990Oct05.221120.25060@xenitec.on.ca> root@zswamp.fidonet.org (Geoffrey Welsh) writes:
>In article <1990Oct5.101354.593@contact.uucp> rrwood@contact.uucp (roy wood) writes:
>>Does anyone out there know of any other good examples that
>>show the reak usefulness of recursion?
>
>   The Towers of Hanoi.

   Actually, the iterative solution to the Towers is probably faster on
most machines, takes less memory (no stack required), and generates
exactly the same moves as the recursive version (in fact, I first
noticed it by watching the output from a recursive solver.) The
iterative solution is:

  1. Move disk 1 (the small disk) to the right (or to the leftmost pin
if it's already on the rightmost).
  2. Move something else.
  3. Repeat until done.

    and yes, there's always only one move possible in step 2. It's easy to
see that if you start doing it this way and then deviate, you're going
backwards. Dunno if that constitutes a proof of optimality or anything =8)


    not to speak against recursion, of course. But *some* recursive solutions
have "better" iterative solutions. (Although it seems that recursive solutions
are usually easier to understand; it's more obvious why they're correct...)

-- 
 wiml@milton.acs.washington.edu       Seattle, Washington   
     (William Lewis)   |  47 41' 15" N   122 42' 58" W  
"These 2 cents will cost the net thousands upon thousands of 
dollars to send everywhere. Are you sure you want to do this?"