home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / lang / c / 16310 < prev    next >
Encoding:
Text File  |  1992-11-10  |  4.2 KB  |  124 lines
  1. Path: sparky!uunet!ferkel.ucsb.edu!taco!rock!concert!rutgers!modus!gear!cadlab!martelli
  2. From: martelli@cadlab.sublink.org (Alex Martelli)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: To Recurse or NOT to recurse?
  5. Message-ID: <1992Nov10.083001.12459@cadlab.sublink.org>
  6. Date: 10 Nov 92 08:30:01 GMT
  7. References: <1992Nov6.185136.8055@netcom.com> <geyke2W00VQsEhTcIK@andrew.cmu.edu>
  8. Organization: CAD.LAB S.p.A., Bologna, Italia
  9. Lines: 113
  10.  
  11. rickr+@CMU.EDU (Richard Dale Romero) writes:
  12.  
  13. :Excerpts from netnews.comp.lang.c: 6-Nov-92 To Recurse or NOT to
  14. :recurse? Stephen Schow@netcom.com (577)
  15. :
  16. :> What is better to do when traversing a linked list..... SHould I use
  17. :> recursion to search down through the list for the last node, or should I
  18. :use a while loop?  What or the pro's and con's of each?
  19. :
  20. :Some compilers are really smart, and they will turn your code into (if
  21. :it is tail recursion) into a while loop.  Others won't.  If it doesn't,
  22. :are you wasting space?  Yes.  How much?  Well, you're using O(N) space
  23. :when it can be done in O(1) space.  That's a lot as far as I'm
  24. :concerned.  And speed?  Bit trickier, and dependent on the machine you
  25. :use, but I'd lay odds on the while loop, say 10:1, that it'd be faster.
  26.  
  27. Right.  Tail recursion can be *mechanically* eliminated anyway; if you're
  28. not sure that your target compilers will do it, do it yourself!  In the
  29. general case, you can first put the tailrecursive function into the form:
  30.  
  31. returned_value_t
  32. function(argument_vector)
  33. {
  34.     first_block_of_code;
  35.     if(recurse_cond)
  36.     return function(other_arguments);
  37.     second_block_of_code;
  38.     return something_else;
  39. }
  40.  
  41. which is provably equivalent to:
  42.  
  43. returned_value_t
  44. function(argument_vector)
  45. {
  46.     do {
  47.     first_block_of_code;
  48.     } while(recurse_cond && ((argument_vector=other_arguments),1));
  49.     second_block_of_code;
  50.     return something_else;
  51. }
  52.  
  53. where the "vector assignment" to the arguments can be expressed as a
  54. series of comma-operator-separated normal assignments to the arguments.
  55. You can most often simplify further.
  56. C is particularly well-suited to this transformation thanks to the
  57. uniform value-passing-semantics of arguments; in Pascal, e.g., you would
  58. have to account for "var" arguments which make it a bit more tricky from
  59. a formal point of view - in C the indirectness implicit in the var arg.
  60. is made explicit, simplifying things.
  61.  
  62. Let's apply this technique to "return pointer to last node of linked list".
  63. Say we have the type:
  64. struct node {
  65.     whatever_t contents;
  66.     struct node *next;
  67. }
  68.  
  69. then the obvious find-last-node recursive implementation is:
  70.  
  71. struct node *
  72. find_last_node(struct node *list_ptr)
  73. {
  74.     if(list_ptr && list_ptr->next)
  75.     return find_last_node(list_ptr->next);
  76.     return list_ptr;
  77. }
  78.  
  79. Here both blocks of code are empty, so the recursion elimination gives:
  80.  
  81. struct node *
  82. find_last_node(struct node *list_ptr)
  83. {
  84.     do {
  85.     } while(list_ptr && list_ptr->next &&
  86.         ((list_ptr = list_ptr->next),1));
  87.     return list_ptr;
  88. }
  89.  
  90. The funny/fancy do-while with empty body and embedded assignment cries
  91. out to be rewritten, of course, to give:
  92.  
  93. struct node *
  94. find_last_node(struct node *list_ptr)
  95. {
  96.     while(list_ptr && list_ptr->next)
  97.     list_ptr = list_ptr->next;
  98.     return list_ptr;
  99. }
  100.  
  101. Now the double-test in the while-condition stands out; each time except
  102. the first, we are testing TWICE for non-NULL list_ptr (since each
  103. time we test for non-NULL ->next, then we put ->next into list_ptr
  104. and test for it again).  We can almost halve the work by only testing
  105. for list_ptr itself at the beginning, and in the loop only for ->next:
  106.  
  107. struct node *
  108. find_last_node(struct node *list_ptr)
  109. {
  110.     if(list_ptr)
  111.         while(list_ptr->next)
  112.         list_ptr = list_ptr->next;
  113.     return list_ptr;
  114. }
  115.  
  116. One can of course build this cleanest and most effective solution in many
  117. other ways (for example from reasoning backwards to the postcondition we
  118. want, "!list_ptr || !(list_ptr->next)", and designing the if() and while()
  119. to suit), but I find the way in which it springs from mechanical recursion
  120. elimination and a little observation quite didactically enlightening...
  121. -- 
  122. Email: martelli@cadlab.sublink.org                   Phone: ++39 (51) 6130360
  123. CAD.LAB s.p.a., v. Ronzani 7/29, Casalecchio, Italia   Fax: ++39 (51) 6130294 
  124.