home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / lang / c / 16394 < prev    next >
Encoding:
Text File  |  1992-11-12  |  2.3 KB  |  62 lines
  1. Newsgroups: comp.lang.c
  2. Path: sparky!uunet!inmos!titan.inmos.co.uk!news
  3. From: conor@lion.inmos.co.uk (Conor O'Neill)
  4. Subject: Re: To Recurse or NOT to recurse?
  5. Message-ID: <1992Nov12.155509.16761@titan.inmos.co.uk>
  6. Sender: news@titan.inmos.co.uk
  7. Reply-To: conor@inmos.co.uk (Conor O'Neill)
  8. Organization: INMOS Limited, Bristol, UK.
  9. References: <1992Nov6.185136.8055@netcom.com> <4223@litchi.bbn.com> <10920@baird.cs.strath.ac.uk> <BxKAJ2.7H@netnews.jhuapl.edu>
  10. Date: Thu, 12 Nov 1992 15:55:09 GMT
  11. Lines: 49
  12.  
  13. In article <BxKAJ2.7H@netnews.jhuapl.edu> bandy@netnews.jhuapl.edu (Mike Bandy) writes:
  14. >I've used C on a few platforms and have never seen an optimization that
  15. >converts recursion to anything but an optimized recursion.  What you're 
  16. >saying is that the optimizer will replace user-defined function calls
  17. >with in-line code.  Can someone give an example of a compiler (and perhaps 
  18. >some code) that verifies this?
  19.  
  20. The INMOS optimising ANSI C compiler produces essentially identical code
  21. for the following two examples; it happily optimises the tail recursion.
  22.  
  23. #include <stdlib.h>
  24. typedef int data;
  25. typedef struct tree_s
  26.   {
  27.     data *d;
  28.     struct tree_s *left;
  29.     struct tree_s *right;
  30.   } tree_t;
  31.  
  32. /* recursive function */
  33.  
  34. tree_t *find(tree_t *t, data *d) {
  35.         if (t == NULL)                          /* sentinel */
  36.                 return NULL;
  37.         else if (t->d == d)                     /* node found? */
  38.                 return t;
  39.         else if (t->d > d)                      /* search left */
  40.                 return find(t->left, d);
  41.         else                                    /* search right */
  42.                 return find(t->right, d);
  43. }
  44.  
  45. /* non-recursive function */
  46.  
  47. tree_t *find(tree_t *t, data *d) {
  48.         while (t != NULL)
  49.                 if (t->d == d)                  /* node found? */
  50.                         return t;
  51.                 else if (t->d > d)              /* search left */
  52.                         t= t->left;
  53.                 else                            /* search right */
  54.                         t= t->right;
  55.         return NULL;                            /* sentinel */
  56. }
  57.  
  58. ---
  59. Conor O'Neill, Software Group, INMOS Ltd., UK.
  60. UK: conor@inmos.co.uk        US: conor@inmos.com
  61. "It's state-of-the-art" "But it doesn't work!" "That is the state-of-the-art".
  62.