hello,
being brain-washed by C/C++, i have a fear of recursion, and a general
impression that it is slower and more wasteful than iteration.
i am new to lisp programming. in lisp, is it a good style to write
recursive functions? especially in 'final' (ready to ship) versions
of programs? i understand that a good compiler would optimise tail
recursion away automatically, but i am talking about true recursion,
where i would have to maintain my own stack, if i used iteration. can
it run into the stack overflow problem at run time, for example?
thanks
konst
"Konst Sushenko" <·····@worldnet.att.net> writes:
> being brain-washed by C/C++, i have a fear of recursion, and a general
> impression that it is slower and more wasteful than iteration.
>
Recursion is also more powerful than iteration. In general, CL has a
number of good iteration constructs like DOLIST, DOTIMES, DO, LOOP and
you should use them when appropriately.
> i am new to lisp programming. in lisp, is it a good style to write
> recursive functions? especially in 'final' (ready to ship) versions
> of programs? i understand that a good compiler would optimise tail
> recursion away automatically, but i am talking about true recursion,
> where i would have to maintain my own stack, if i used iteration. can
> it run into the stack overflow problem at run time, for example?
A good implementation will probably implement recursion more
efficiently than you could do it yourself by using your own stack. I
think the only way you're going to get stack overflow is by trying to
evaluate the Ackerman function or something like that. I've certainly
not seen it in real life.
--
Lieven Marchand <···@bewoner.dma.be>
Lambda calculus - Call us a mad club
"Lieven Marchand" ...
> I think the only way you're going to get stack overflow is by trying to
> evaluate the Ackerman function or something like that. I've certainly
> not seen it in real life.
Except of course, in the case where the recursion is not terminated
properly.
The equivalent of an endless loop in iteration.
But hopefully testing will detect this.
Yet, the possibility suggests to me that I must be extra-careful to make the
termination conditions of my recursions very clear and obvious.
A complex recursion might pass certain tests, but fail in certain cases.
Does this make sense to experienced Lispers?
I'm very new to Lisp, so I am just stating what I hope is obvious to others.
--
Best Wishes,
David Kreth Allen
Software Consultant
Minneapolis, Minnesota - USA
"David K Allen" <·······@visi.com> writes:
> Yet, the possibility suggests to me that I must be extra-careful to make the
> termination conditions of my recursions very clear and obvious.
> A complex recursion might pass certain tests, but fail in certain cases.
> Does this make sense to experienced Lispers?
Not really. This is just the same for iteration.
Consider
(defun foo (list)
(cond ((null list) 0)
(t (1+ (foo (cdr list))))))
If your list is cyclic, this will fail to terminate. If you write it
with iteration, let's say in C style like this
i=0;
while(list!=NULL)
{
++i;
list=list->next;
}
it will also fail to terminate. In fact, with recursion it is often
more easy to prove termination since recursive algorithm typically
come from a divide and conquer approach, so each invocation is of a
structurally simpler kind. With iteration, you have to construct loop
invariants and loop variants.
Eiffel even supports this in the loop syntax:
from
x:=a;y:=b
invariant
x>0; y>0
-- gcd(a,b)=gcd(x,y)
variant
x.max(y)
until
x=y
loop
if x>y then x:=x-y else y:=y-x end
end
--
Lieven Marchand <···@bewoner.dma.be>
Lambda calculus - Call us a mad club
Lieven Marchand <···@bewoner.dma.be> writes:
> "David K Allen" <·······@visi.com> writes:
>
> > Yet, the possibility suggests to me that I must be extra-careful to make the
> > termination conditions of my recursions very clear and obvious.
> > A complex recursion might pass certain tests, but fail in certain cases.
> > Does this make sense to experienced Lispers?
>
> Not really. This is just the same for iteration.
>
> Consider
>
> (defun foo (list)
> (cond ((null list) 0)
> (t (1+ (foo (cdr list))))))
>
> If your list is cyclic, this will fail to terminate. If you write it
> with iteration, let's say in C style like this [...]
> it will also fail to terminate. In fact, with recursion it is often
> more easy to prove termination since recursive algorithm typically
> come from a divide and conquer approach, so each invocation is of a
> structurally simpler kind. With iteration, you have to construct loop
> invariants and loop variants.
But it is important to note that CL does not guarantee tail call
elimination, so if you write your code with iteration to cdr down a list,
you will almost certainly lose unless the list is known to be reliably short.
My personal rule of thumb, which I know will alarm some people but
which I still find useful enough to mention, is to freely recurse into
the car but not into the cdr. This is based on a statistical truth
that things tend to be finitely deep (usually more than depth 6 or 7
is unusual--certainly depth 100 is extraordinarily unusual) while
length of 200 or even 2000 might not be unusual.
Kent M Pitman wrote:
>My personal rule of thumb, which I know will alarm some people but
>which I still find useful enough to mention, is to freely recurse into
>the car but not into the cdr. This is based on a statistical truth
>that things tend to be finitely deep (usually more than depth 6 or 7
>is unusual--certainly depth 100 is extraordinarily unusual) while
>length of 200 or even 2000 might not be unusual.
This is a good rule.
From my experience with AutoLISP which has no tail call elimination and
on some releases a very limited stack size (~200):
Recursive operations on lists are typically forbidden like sorting, set
operations, parsing. Even trees will fail.
such as remove, remove-if, member-if, firstn, setnth, flatten,
merge-sort, quick-sort, ...
A lot of typical list functions, which really should be recursive to be
able to read and maintain, had to converted to iterative ones. They are
now faster and safer but a pain to explain to others and to improve.
Just think of this iterative flatten:
(defun STD-FLATTEN (lst / pend new curr) ; / for &aux
(cond
((null lst) nil)
((atom lst) lst)
(T
(setq pend lst new nil)
(while pend
(if (atom pend) ; for processing '(1 2 . 3)
(setq curr pend pend nil)
(setq curr (car pend) pend (cdr pend)))
(while (consp curr)
(if (cdr curr)
(setq pend (cons (cdr curr) pend)))
(setq curr (car curr)))
;;now curr is atom
(setq new (cons curr new)))
(reverse new))))
in contrast to:
(defun STD-FLATTEN (lst)
(cond ((null lst) nil)
((atom lst) (list lst))
(T (append (std-flatten (car lst)) (std-flatten (cdr lst))))))
I have even worse examples but longer examples.
So: recursion is good. If your system supports it.
--
Reini Urban
http://xarch.tu-graz.ac.at/autocad/news/faq/autolisp.html
I've had recursive functions crap out even in ACL on large
Unix workstations with plenty of swap space because there was just too
much data.
Loop and the Do family are pretty good for iteration, even
if the resulting source code are not always pretty.
sl
Steve Long <·········@isomedia.com> writes:
> I've had recursive functions crap out even in ACL on large
> Unix workstations with plenty of swap space because there was just too
> much data.
> Loop and the Do family are pretty good for iteration, even
> if the resulting source code are not always pretty.
Unless, of course, your problem is inherently recursive. E.g. Tree
traversal.
Cheers
--
Marco Antoniotti =============================================================
NYU Bioinformatics Group tel. +1 - 212 - 998 3488
719 Broadway 12th Floor fax +1 - 212 - 995 4122
New York, NY 10003, USA http://galt.mrl.nyu.edu/valis
Centuries ago, Nostradamus foresaw a time when Lieven Marchand would say:
>"David K Allen" <·······@visi.com> writes:
>> Yet, the possibility suggests to me that I must be extra-careful to
>> make the termination conditions of my recursions very clear and
>> obvious. A complex recursion might pass certain tests, but fail in
>> certain cases. Does this make sense to experienced Lispers?
>
>Not really. This is just the same for iteration.
>
>Consider
>
>(defun foo (list)
> (cond ((null list) 0)
> (t (1+ (foo (cdr list))))))
>
>If your list is cyclic, this will fail to terminate. If you write it
>with iteration, let's say in C style like this
>
>i=0;
>while(list!=NULL)
>{
> ++i;
> list=list->next;
>}
>
>it will also fail to terminate. In fact, with recursion it is often
>more easy to prove termination since recursive algorithm typically
>come from a divide and conquer approach, so each invocation is of a
>structurally simpler kind. With iteration, you have to construct loop
>invariants and loop variants.
>
>Eiffel even supports this in the loop syntax:
>
>from
> x:=a;y:=b
>invariant
> x>0; y>0
> -- gcd(a,b)=gcd(x,y)
>variant
> x.max(y)
>until
> x=y
>loop
> if x>y then x:=x-y else y:=y-x end
>end
Counterpoint: I'd say that the _issue_ makes a fair bit of sense; yes,
indeed, it _is_ important to validate the termination criteria, and to
make them quite clear.
This is true both for iterative _and_ recursive expressions.
If the "gentle programmer" is not particularly comfortable with
recursion, then he may not feel as comfortable with recursive
representations, and may feel a need for somewhat excessive care.
With greater experience, and greater "comfort levels," it should
become more clear that the dangers of "nontermination" are pretty much
equivalent whether a particular loop is presented in recursive or
iterative manner.
This equivalence isn't merely "apparent," but represents an underlying
reality since any iteration may be expressed as a recursion. You find
this demonstrated by the fact that Common Lisp and Scheme both
transform iterative control structures like DO, LOOP, and DOLIST into
recursive representations.
For instance, expanding the following "iterative" code:
(macroexpand-1
'(do ((j 0 (+ j 1)))
(nil) ;Do forever.
(format t "~%Input ~D:" j)
(let ((item (read)))
(if (null item) (return) ;Process items until NIL seen.
(format t "~&Output ~D: ~S" j item)))))
Generates what is essentially a recursive representation:
(BLOCK
NIL
(LET ((J 0))
(TAGBODY #:G1087
(IF NIL
(GO #:G1088))
(FORMAT T "~%Input ~D:" J)
(LET ((ITEM (READ)))
(IF (NULL ITEM)
(RETURN)
(FORMAT T "~&Output ~D: ~S" J ITEM)))
(PSETQ J (+ J 1))
(GO #:G1087)
#:G1088
(RETURN-FROM NIL (PROGN)))))
With Scheme, there is the designed-in assumption that implementations
are required to be tail-recursive, which means that if a recursive
construct may be "proven" to be iterative, the implementation _must_
treat it as being iterative, which means that the amount of "stack"
used by an iterative bit of code is strictly bounded.
With Common Lisp, tail recursion is not required, which means that _in
theory_, the use of memory may not be bounded. In practice, it is not
unusual for implementations to take advantage of tail recursion to
transform some recursion into iteration.
The other issue that David Allen was probably concerned about was that
of "eating up" the stack, as can occur in C/C++ if you take recursion
down too many levels. In C (and friends), calling a function results
in the allocation of a stack frame that commonly eats up a strictly
limited "stack" region. This is _not_ a concern in Lisp the way it is
in C; in Lisp, such memory is likely to be heap-allocated, and thus
has the whole of the memory space to play with.
--
(concatenate 'string "cbbrowne" ·@" "acm.org")
<http://www.hex.net/~cbbrowne/lisp.html>
"Sigh. I like to think it's just the Linux people who want to be on
the `leading edge' so bad they walk right off the precipice."
-- Craig E. Groeschel
In article <····················@news5.giganews.com>,
········@hex.net wrote:
> This equivalence isn't merely "apparent," but represents an underlying
> reality since any iteration may be expressed as a recursion. You find
> this demonstrated by the fact that Common Lisp and Scheme both
> transform iterative control structures like DO, LOOP, and DOLIST into
> recursive representations.
While Scheme does indeed implement iteration through tail-recursive
procedure calls, I'm quite sure that Common Lisp *doesn't* say "thou
shalt transform iterative control structures into recursive ones".
> For instance, expanding the following "iterative" code:
> (macroexpand-1
> '(do ((j 0 (+ j 1)))
> (nil) ;Do forever.
> (format t "~%Input ~D:" j)
> (let ((item (read)))
> (if (null item) (return) ;Process items until NIL seen.
> (format t "~&Output ~D: ~S" j item)))))
>
> Generates what is essentially a recursive representation:
> (BLOCK
> NIL
> (LET ((J 0))
> (TAGBODY #:G1087
> (IF NIL
> (GO #:G1088))
> (FORMAT T "~%Input ~D:" J)
> (LET ((ITEM (READ)))
> (IF (NULL ITEM)
> (RETURN)
> (FORMAT T "~&Output ~D: ~S" J ITEM)))
> (PSETQ J (+ J 1))
> (GO #:G1087)
> #:G1088
> (RETURN-FROM NIL (PROGN)))))
...and this is recursive how? :-)
> With Scheme, there is the designed-in assumption that implementations
> are required to be tail-recursive, which means that if a recursive
> construct may be "proven" to be iterative, the implementation _must_
> treat it as being iterative, which means that the amount of "stack"
> used by an iterative bit of code is strictly bounded.
I think it's a bit stronger than that. I believe that Scheme requires
that it be iterative even if it can't prove at compile time that the
code is iterative. Many implementations fudge this issue a bit for
efficiency's sake, since a strict interpretation pretty much requires
CPS conversion. I could be wrong here, I haven't done much Scheme since
the R3RS days.
> With Common Lisp, tail recursion is not required, which means that _in
> theory_, the use of memory may not be bounded. In practice, it is not
> unusual for implementations to take advantage of tail recursion to
> transform some recursion into iteration.
>
> The other issue that David Allen was probably concerned about was that
> of "eating up" the stack, as can occur in C/C++ if you take recursion
> down too many levels. In C (and friends), calling a function results
> in the allocation of a stack frame that commonly eats up a strictly
> limited "stack" region. This is _not_ a concern in Lisp the way it is
> in C; in Lisp, such memory is likely to be heap-allocated, and thus
> has the whole of the memory space to play with.
Again, this is definitely an implementation issue: A program in CPS
form doesn't have a conventional stack, while a Lisp->C system *may*
inherit the stack limitations from it's hosting language. OTOH, I've
known C++ programs to run with (and need) multi-megabyte stacks;
fortunately NT allocates stack space on demand.
Sent via Deja.com http://www.deja.com/
Before you buy.
David K Allen wrote:
> "Lieven Marchand" ...
> > I think the only way you're going to get stack overflow is by trying to
> > evaluate the Ackerman function or something like that. I've certainly
> > not seen it in real life.
>
> Except of course, in the case where the recursion is not terminated
> properly. The equivalent of an endless loop in iteration.
> But hopefully testing will detect this.
> Yet, the possibility suggests to me that I must be extra-careful to make the
> termination conditions of my recursions very clear and obvious.
> A complex recursion might pass certain tests, but fail in certain cases.
> Does this make sense to experienced Lispers?
> I'm very new to Lisp, so I am just stating what I hope is obvious to others.
>
> --
> Best Wishes,
> David Kreth Allen
> Software Consultant
> Minneapolis, Minnesota - USA
misused recursion can be REALLY bad. I took over a 20kloc lisp program 10 years
ago last week, realized that one day my predecessors had discovered recursion,
fell in love with it, and every function they wrote after that was recursive.
tail recursive. whether that was appropriate or not. once I realized this, and
began rewriting them, speed gains appeared right away.
well, that was on the 'bolics, when tail-recursion was reputed to not be
optimizing :( anyway, it was a lot simpler to rewrite from recursion to
iteration that to try to figure out how to fix the recursion.
this is not to say that recursion is bad--but know what you're doing, and what
your data looks like. As Kent points out, you could be recursing over a long
list of data, and easily run out of stack space (in the theoretical case, that
shouldn't actually happen, but we don't write code on theretical machines, our
physical CL implementations actually have stack limits), where iteration
wouldn't, and depending on the content of the data, you might not know for a
while...
i don't use "bi-directional" recursion (i.e., both car and cdr) very often, and
I have to be very very careful to avoid bugs, because it's easy to do it wrong.
and you can also run out of stack with a recursive *interpreted* function, even
if the data isn't so large that you have *that* problem, because you end up with
a lot more in the way of intermediate stack-frames that the compiler would
eliminate. at least the LispM would give you a proceed option to grow the
stack, which usually solved the problem.
I'd also suggest that if you DO have a recursion-blowout problem, that you think
about your data for a bit and maybe redesign it....
-- clint