home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / programm / 2475 < prev    next >
Encoding:
Internet Message Format  |  1992-08-25  |  1.4 KB
  1. Path: sparky!uunet!mcsun!sun4nl!cwi.nl!tromp
  2. From: tromp@cwi.nl (John Tromp)
  3. Newsgroups: comp.programming
  4. Subject: Re: Teaching the basics
  5. Message-ID: <7154@charon.cwi.nl>
  6. Date: 26 Aug 92 08:39:58 GMT
  7. References: <1992Aug19.154830.11787@uwm.edu> <MJN.92Aug23031941@pseudo.uucp> <7116@charon.cwi.nl> <1992Aug25.174243.10436@uwm.edu>
  8. Sender: news@cwi.nl
  9. Lines: 25
  10.  
  11. markh@csd4.csd.uwm.edu (Mark) writes:
  12.  
  13. >In article <7116@charon.cwi.nl> tromp@cwi.nl (John Tromp) writes:
  14. >>>On top of it all, the recursive version does not have an arbitrary
  15. >>>limit on the number of disks, and can be easily translated to any
  16. >>>language supporting recursion.
  17. >>
  18. >>Well, nobody in his right mind would ever run hanoi on 32 discs or more:-)
  19. >>
  20. >>One of the prime applications of recursion, IMHO,
  21. >>and where you cannot hope to replace it by anything else,
  22. >>is in a tree search algorithm like alpha beta or plain old minimax.
  23.  
  24. >Wrong.  In fact, the non-recursive version (tree search) is far smaller and
  25. >simpler.  No stacks either.
  26.  
  27. Maybe I didn't make myself clear enough. I wasn't referring to mere
  28. tree *traversals* but to algorithm that keep some state information at each
  29. node. For instance, the alpha-beta algorithm keeps track of upper and lower
  30. bounds in each call, not globally. In contrast to towers-of-hanoi, this
  31. information does not derive from the current location of the search.
  32.  
  33. These are the types of problem that recursion is most suited to.
  34.  
  35. -John Tromp
  36.