home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / lang / c / 16266 < prev    next >
Encoding:
Internet Message Format  |  1992-11-10  |  2.4 KB
  1. Path: sparky!uunet!mcsun!sun4nl!and!jos
  2. From: jos@and.nl (Jos Horsmeier)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: To Recurse or NOT to recurse?
  5. Message-ID: <3842@dozo.and.nl>
  6. Date: 10 Nov 92 10:34:58 GMT
  7. References: <1992Nov6.185136.8055@netcom.com> <1992Nov10.003842.19169@asc386>
  8. Organization: AND Software BV Rotterdam
  9. Lines: 74
  10.  
  11. In article <1992Nov10.003842.19169@asc386> mosmith@asc386 (Matt Smith) writes:
  12. |The question is whether to recusively desend a linked-list or
  13. |to do it iteraviely( a while loop).  My expeience has
  14. |shown that the while loop is better in the long run.
  15. |
  16. |Reason:  Recursion uses the stack to store the recusive stuff (hope
  17. |that's not too techy) which tends to blow up.  I prefer the other
  18. |way
  19.  
  20. As a rule of thumb, I always use the following reasoning:
  21.  
  22.     `Never use recursion when the size of the stack is 
  23.     linear proportional to the size of the problem.'
  24.  
  25. Traversing a linked list with n elements takes up to n slots on the
  26. stack (and even a bit more for administration purposes) so I don't
  27. use recursion here. 
  28.  
  29. Even when recursion is `needed', most of the time one of the recursive
  30. branches can be eliminated, e.g finding an element in a sorted binary
  31. tree can (intuitively) be written as:
  32.  
  33. tree_t *find(tree_t *t, data *d) {
  34.  
  35.     if (!t)                    /* 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(tree->right, d);
  43.  
  44. }
  45.  
  46. The tail recursion can be eliminated by:
  47.  
  48. tree_t *find(tree_t *t, data *d) {
  49.  
  50.     for (; t; t= t->right)             /* search right otherwise */
  51.  
  52.         if (t->d == d)            /* node found? */
  53.             return t;
  54.         else if (t->d > d)        /* search left */
  55.             return find(t->left, d);
  56.  
  57.     return NULL;                /* sentinel */
  58. }
  59.  
  60. Taking this example a bit further, the recursion can be totally
  61. eliminated by the following transformation:
  62.  
  63. tree_t *find(tree_t *t, data *d) {
  64.  
  65.     while (t) 
  66.         if (t->d == d)            /* node found */
  67.             return t;
  68.         else if (t->d > d)        /* search right */
  69.             t= t->left;
  70.         else                /* search left */
  71.             t= t->right;
  72.  
  73.     return NULL;                /* sentinel */
  74. }
  75.  
  76. I'm a bit of an `optimization freak' myself and I always try to eliminate
  77. as much recursion as possible, because I still believe (and I know I'm
  78. wrong most of the time) that function calls cause a teensy weensy bit
  79. more overhead than simple iteration. But when the recursion violates
  80. my rule of thumb, I don't even think about recursion any further.
  81.  
  82. kind regards,
  83.  
  84. Jos aka jos@and.nl
  85.