home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / programm / 2473 < prev    next >
Encoding:
Internet Message Format  |  1992-08-25  |  2.2 KB
  1. Path: sparky!uunet!munnari.oz.au!goanna!ok
  2. From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe)
  3. Newsgroups: comp.programming
  4. Subject: Re: Teaching the basics
  5. Message-ID: <14194@goanna.cs.rmit.oz.au>
  6. Date: 26 Aug 92 10:56:56 GMT
  7. References: <1992Aug17.123916.14815@husc13.harvard.edu> <7116@charon.cwi.nl>
  8. Organization: Comp Sci, RMIT, Melbourne, Australia
  9. Lines: 42
  10.  
  11. In article <7116@charon.cwi.nl>, tromp@cwi.nl (John Tromp) writes:
  12. > mjn@pseudo.uucp (Murray Nesbitt) writes:
  13. > >markh@csd4.csd.uwm.edu (Hunk) writes:
  14. > >>In article <14066@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes:
  15. > >>I think recursion is a farce.  And just to rub it in, here's the Towers of
  16. > >>Hanoi (up to N = 31, I'm assuming long integers are 32 bits) without it (in C)
  17.  
  18. > Ok, maybe Richard meant something like this:
  19.  
  20. Please get your attribution straight.  That _wasn't_ me.  I'm the one who
  21. said that if you don't understand recursion, you don't understand programming.
  22.  
  23. >  void hanoi(n)
  24. > {
  25. >   for (x = 1; x < (1<<n); x++)
  26. >     printf("move a disc from %d to %d\n", (x&x-1)%3, ((x|x-1)+1)%3);
  27. > }
  28. > 
  29. <some one else>
  30. > >Beauty is in the eye of the beholder, but in my opinion the recursive
  31. > >version is a little easier to follow, to say the least.
  32. > 
  33. > Hmmm, guess I'll have to agree to that:-)
  34. > But efficient it's not, particularly in its use of (stack) space.
  35.  
  36. The recursive version of Towers of Hanoi for N disks takes o(N) stack
  37. frames; a typical stack frame (assuming a good compiler) would be two or
  38. three words of memory.  Using ~2N words of memory for a program that takes
  39. O(2**N) time doesn't strike _me_ as grossly inefficient.
  40.  
  41. From my perspective (heavily influenced by Lisp/Scheme/T, NPL/Hope/ML,
  42. Prolog, and similar languages), the only differences between C's "for"
  43. and Scheme's "named-LET" are (a) punctuation & spelling and (b) C's
  44. "for" loop is less expressive for iterations that Scheme's nominally
  45. recursive (but actually iterative) notation.
  46.  
  47. Besides, the simple recursive version is not as limited by the size of
  48. integers.  The machine I'm using as a _terminal_emulator_ can go through
  49. hanoi(32) in under an hour, so don't think that 32-bit integers are enough...
  50.  
  51. -- 
  52. You can lie with statistics ... but not to a statistician.
  53.