Re: Multivalue tail recursion?

Jeff wrote:
I think you were probably wondering about something that isn't true.

That happens more often than I'd like to admit.

All of this may be interesting, but I don't think it is of great
practical concern, at least not for beginning to intermediate CL
programmers. The danger, if any, may lie in a Schemer coming to Common
Lisp with the idea of using recursion for everything, and then
wondering why the stack gets blown CDRing down a million item list...
It will work in Scheme, but you may have to take special steps to have
it work in Common Lisp.

Thanks. That is helpful to keep in mind. I didn't phrase my question
well. I was specifically wondering what the difference is between
using dolist or some other iteration-based function for list building
and the ML-style method of declaring a recursive function in the local
scope as well as an empty list and then running the recursive function
to build the list. For example,

(set 'foo '(some sort of list))
(let ((accum '()))
(labels ((iter (lst)
(cond
((null (car lst)) accum)
(t (progn
(push (car lst) accum)
(iter (cdr lst)))))))
(set 'bar (iter foo))))

While this is obviously contrived (it just copies list foo to list
bar), the basic idea is that there is a list that gets accumulated,
there is a locally defined iterator function that can be customized to
the exact needs of the programmer (i.e., should it return the value of
the accumulated list, etc.).

I think that most likely, dolist is much faster for iteration. But I
figured that in some situations, this would be an ideal solution. I
was just wondering if there was a specific reason not to do this.

By itself, using recursive versions of algorithms doesn't buy you a lot, especially not if you use side effects inside the recursively defined functions.

What is interesting about a functional programming style is that if you don't use any side effects (or any other effects), you can be sure that for every set of concrete parameters, a function will always return the same result. This makes it easier to prove properties about such functions. If you use iterative constructs, you use side effects, so that makes such proofs harder.

To be able to express iterations without using side effects, you have to resort to recursive function definitions to keep the definitions effect-free. When you define a function recursively, you need a base case (in your code the test for the empty list), and a general case (if the list is not empty). This gives you a natural way of proving properties via induction.

If you don't need to (formally) prove properties of your programs, you can ignore such considerations - then iteration constructs are typically easier to read.


Pascal

--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
.

Relevant Pages

  • Re: Interesting article by Joel Spolsky: The Perils of JavaSchools
    ... >>> Most Java(any imperative language) programmers will instinctively opt ... Recursion is useful in mathematical definitions, ... > perverted way in which many programmers go about effecting iteration. ...
    (comp.programming)
  • Re: Is anything easier to do in java than in lisp?
    ... How long ago was your Lisp class? ... The funny thing is that anyone posting on c.l.lisp a recursive solution ... I got a huge kick out of recursion when I started my Lisp family ... recursion's sake, but then neither do I eschew iteration where it will, ...
    (comp.lang.java)
  • Re: Is anything easier to do in java than in lisp?
    ... How long ago was your Lisp class? ... The funny thing is that anyone posting on c.l.lisp a recursive solution ... I got a huge kick out of recursion when I started my Lisp family ... recursion's sake, but then neither do I eschew iteration where it will, ...
    (comp.lang.lisp)
  • Re: Do you think that the CHristian faith is declining in the United Kingdom?
    ... Then you get edicts from management like "Don't use recursion because it ... could frighten the programmers". ... Iteration is safer. ...
    (uk.religion.christian)
  • Re: newbie question : summing elements in a list
    ... > place that recursion is required nor even always encouraged. ... > Recursive solutions can use stack and you can run out of stack. ... > users are taught that recursion is just another syntax for iteration, ... > In my personal view, the right solution for Common Lisp, if anything ...
    (comp.lang.lisp)