home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / programm / 2484 < prev    next >
Encoding:
Text File  |  1992-08-26  |  1.7 KB  |  43 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!caen!uwm.edu!csd4.csd.uwm.edu!markh
  3. From: markh@csd4.csd.uwm.edu (Mark)
  4. Subject: Re: Teaching the basics
  5. Message-ID: <1992Aug26.175253.29133@uwm.edu>
  6. Sender: news@uwm.edu (USENET News System)
  7. Organization: Computing Services Division, University of Wisconsin - Milwaukee
  8. References: <1992Aug17.123916.14815@husc13.harvard.edu> <7116@charon.cwi.nl> <14194@goanna.cs.rmit.oz.au>
  9. Date: Wed, 26 Aug 1992 17:52:53 GMT
  10. Lines: 31
  11.  
  12. In article <14194@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes:
  13. >Please get your attribution straight.  That _wasn't_ me.  I'm the one who
  14. >said that if you don't understand recursion, you don't understand programming.
  15. >
  16. >>  void hanoi(n)
  17. >> {
  18. >>   for (x = 1; x < (1<<n); x++)
  19. >>     printf("move a disc from %d to %d\n", (x&x-1)%3, ((x|x-1)+1)%3);
  20. >> }
  21. >> 
  22. >Besides, the simple recursive version is not as limited by the size of
  23. >integers.  The machine I'm using as a _terminal_emulator_ can go through
  24. >hanoi(32) in under an hour, so don't think that 32-bit integers are enough...
  25.  
  26. It's easy enough to extend it to arbitrary precision integers since the
  27. operations involved (decrement, logical shifts, logical or) are easily
  28. extended, especially if you're doing it in assembly.
  29.  
  30. You could even bring these operations out to the source level in a language
  31. like C++, using the same operator symbols (+, <<, >>, etc).
  32.  
  33. Generally a recursion with N essential entry points has its entry-point stack
  34. coded as follows:
  35.  
  36. long_word X;
  37. CLEAR()     { X = 0; }
  38. PUSH(int N) { X = N*X + 1; }
  39. EMPTY()     { return X == 0; }
  40. POP()       { int Top; X--, Top = X%N, X /= N; return Top; }
  41.  
  42. A recursion with a single entry point therefore uses a counter.
  43.