home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / lang / c / 16156 < prev    next >
Encoding:
Internet Message Format  |  1992-11-08  |  1.8 KB
  1. Path: sparky!uunet!cis.ohio-state.edu!rutgers!princeton!csservices!kastle!blume
  2. From: blume@kastle.Princeton.EDU (Matthias Blume)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: To Recurse or NOT to recurse?
  5. Message-ID: <1992Nov7.205704.19368@csservices.Princeton.EDU>
  6. Date: 7 Nov 92 20:57:04 GMT
  7. References: <1992Nov6.185136.8055@netcom.com> <geyke2W00VQsEhTcIK@andrew.cmu.edu>
  8. Sender: news@csservices.Princeton.EDU (USENET News System)
  9. Reply-To: blume@kastle.Princeton.EDU (Matthias Blume)
  10. Organization: Dept. of Computer Science, Princeton University
  11. Lines: 28
  12.  
  13. In article <geyke2W00VQsEhTcIK@andrew.cmu.edu>, Richard Dale Romero
  14. <rickr+@CMU.EDU> writes:
  15. |> Excerpts from netnews.comp.lang.c: 6-Nov-92 To Recurse or NOT to
  16. |> recurse? Stephen Schow@netcom.com (577)
  17. |> 
  18. |> > What is better to do when traversing a linked list..... SHould I use
  19. |> > recursion to search down through the list for the last node, or should I
  20. |> use a while loop?  What or the pro's and con's of each?
  21. |> 
  22. |> Some compilers are really smart, and they will turn your code into (if
  23. |> it is tail recursion) into a while loop.  Others won't.  If it doesn't,
  24. |> are you wasting space?  Yes.  How much?  Well, you're using O(N) space
  25. |> when it can be done in O(1) space.  That's a lot as far as I'm
  26. |> concerned.  And speed?  Bit trickier, and dependent on the machine you
  27. |> use, but I'd lay odds on the while loop, say 10:1, that it'd be faster.
  28. |> 
  29. |> -rick
  30. |> 
  31. |> 
  32.  
  33. I would not count on such a ``smart'' C compiler, because there are lots
  34. of issues, which can prevent it from generating loop code for a tail recursive
  35. function.  (Think about addresses of local variables, setjmp/longjmp and
  36. alloca).
  37. In a language like Scheme, which is *defined* to produce code, that runs in
  38. constant space for tail recursions, you can (and in fact must) count on it.
  39.  
  40. -Matthias
  41.