home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / programm / 2380 < prev    next >
Encoding:
Text File  |  1992-08-19  |  1.9 KB  |  59 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!gumby!wupost!uwm.edu!csd4.csd.uwm.edu!markh
  3. From: markh@csd4.csd.uwm.edu (Hunk)
  4. Subject: Re: Teaching the basics
  5. Message-ID: <1992Aug19.154830.11787@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> <14066@goanna.cs.rmit.oz.au>
  9. Date: Wed, 19 Aug 1992 15:48:30 GMT
  10. Lines: 47
  11.  
  12. In article <14066@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes:
  13. >If you don't know recursion, you don't know programming.  It is one of the
  14. >simpler concepts in computing.  (Much simpler than mutable variables, IMHO.)
  15.  
  16. I think recursion is a farce.  And just to rub it in, here's the Towers of
  17. Hanoi (up to N = 31, I'm assuming long integers are 32 bits) without it (in C):
  18.  
  19. #include <stdio.h>
  20.  
  21. /* Move a stack of N objects from tower A to C, using B */
  22. void Hanoi(int N, char A, char B, char C) {
  23.    unsigned long X = 0; char D;
  24. HANOI:
  25.    if (N > 0) {
  26.       D = B, B = C, C = D, N--;
  27.       X = 2*X + 2; goto HANOI; X2: X = (X - 1)/2;
  28.       N++, D = B, B = C, C = D;
  29.       printf("Move %d from %c to %c.\n", N, A, C);
  30.       D = A, A = B, B = D, N--;
  31.       X = 2*X + 1; goto HANOI; X1: X = (X - 1)/2;
  32.       N++, D = A, A = B, B = D;
  33.    }
  34.    if (X&1) goto X1;
  35.    if (X > 0) goto X2;
  36. }
  37.  
  38. main() { Hanoi(5, 'a', 'b', 'c'); }
  39.  
  40. or with the recursion scars removed, and algebraic cancellations carried out,
  41. this:
  42.  
  43. #include <stdio.h>
  44.  
  45. /* Move a stack of N objects from tower A to C, using B */
  46. void Hanoi(int N, char A, char B, char C) {
  47.    unsigned long X = 0; char D;
  48.    while (1) {
  49.       if (N&1) D = B, B = C, C = D;
  50.       for (; N > 0; N--) X = (X + 1) << 1;
  51.       for (; X&1; X >>= 1, N++) D = A, A = B, B = D;
  52.       if (X == 0) break;
  53.       printf("Move %d from %c to %c.\n", N + 1, A, B);
  54.       D = C, C = B, B = A, A = D, X--;
  55.    }
  56. }
  57.  
  58. main() { Hanoi(5, 'a', 'b', 'c'); }
  59.