Re: Iteration in lisp

På Tue, 22 Apr 2008 05:34:34 +0200, skrev Kent M Pitman <pitman@xxxxxxxxxxx>:

"rigaha@xxxxxxxxx" <rigaha@xxxxxxxxx> writes:

If you want to iterate through a list, should you use a recursive
function or a loop?

In Common Lisp, always prefer a loop where practical unless you know
with relative certainty that the problem cannot grow very big. A
recursive function can run out of stack since CL does not guarantee
tail call elimination. Anyone who tells you otherwise is living in a
fantasy world or is telling you something implementation-dependent or
is confusing Lisp with Scheme.

Fantasy world? Nearly all compilers seem to do tail call elimination with the default settings.
You would have to set (declare (optimize (debug 3))) (On LispWorks, but as long as speed > debug it should work on all) to turn it off. Yes, it won't won't on evaluated code and yes, the standard doesn't require it.

That said I generally think looping is a better idea for list traversal, but for other reasons.
Tail recursion requires you to specify the argument to be passed many times. One time through each call. This makes maintenance harder as if you change the type you would need to update ALL calls. In loop you would usually only need one change. So using tail recursion rather than a loop can introduce bugs in complex looping constructs.


--------------
John Thingstad
.

Relevant Pages

  • Re: Python and Scheme
    ... is that tail recursion make debugging more difficult and that rules ... it out from Python. ... (let loop () ...
    (comp.lang.scheme)
  • Re: Javascript recursion limit
    ... a loop is something that repeats - that comes back to the ... An recursive function can do that, if the language allows it. ... ECMAScript does not require an implementation to have tail recursion, ...
    (comp.lang.javascript)
  • Re: Iteration in lisp
    ... recursive function can run out of stack since CL does not guarantee ... archives of this newsgroup for the TAILPROG macro, ... tail recursion with syntax resembling FLET or LABELS can be obtained ...
    (comp.lang.lisp)
  • Re: Programming Puzzle
    ... > tail recursion. ... What is "tail" recursion? ... But to me, recursion is a loop, ... The first iterator is the slow ...
    (comp.lang.c)
  • Re: Programming Puzzle
    ... > tail recursion. ... What is "tail" recursion? ... But to me, recursion is a loop, ... The first iterator is the slow ...
    (comp.lang.cpp)