Re: Simple recursive functions in Lisp

Thanks for that great analysis, Kaz.

Your equivalent iterative implenetation begs the question: assuming
all assignemnts (ie side effects) are local and immediate, is there a
real advantage to functional style recursion over iteration? It seems
to me that it's just as hard - even harder - to keep track of the
recursive state / accumulator than to keep track of the iterative
assignments.

Dogma aside, how have I gained by writing it in the recursive version?

(I'm referring to advantages for the programmer, not differences in
execution speed).

On Feb 7, 6:08 pm, "Kaz Kylheku" <kkylh...@xxxxxxxxx> wrote:
On Feb 7, 2:29 pm, "S. Robert James" <srobertja...@xxxxxxxxx> wrote:

As a Lisp newbie, I implemented reverse as follows:
(defun reverse. (lst)

You can use LIST as a variable name in Common Lisp. Only the function
binding of the symbol COMMON-LISP:LIST is reserved.

"Returns lst reversed"
(if (null (cdr lst))
(list (car lst))
(append (reverse. (cdr lst)) (list (car lst)))))

I noticed that Paul Graham (On Lisp, p.30) implements it as:

(defun good-reverse (lst)
(labels ((rev (lst acc)
(if (null lst)
acc
(rev (cdr lst) (cons (car lst) acc)))))
(rev lst nil)))

Why? My implementation seems clearer. How is Graham's superior?

Graham's is superior because of the extra ACC parameter taken by the
local recursive function REV. Note how the accumulator is used
together with CONS to build up the list without traversing it,
contrary to your approach using APPEND, which has to scan the new list
every time. So you can see that it takes O(N) time.

Secondly, note that his version is tail-recursive. This means that a
good Lisp compiler can turn it into a loop, in which the ACC variable
becomes a loop variable. This means that when Graham's version is
compiled, it will not only run in linear time, but in constant O(1)
stack space.

Your version is not tail recursive because the return value of the
recursive call is used for further computation (doing the APPEND). So
your version requires O(N^2) time (due to the repeated re-scanning of
the growing list to append more items to it) and O(N) stack space (due
to the naive car/cdr recursion).

(Stricly speaking, both approaches use O(N) space since they are
consing up a list that is just as long as the input list. However,
stack space nevertheless has to be considered separately because it
may be in limited supply, and it still waste by a constant factor even
if you don't run out).

Another way to express Graham's algorithm is iteration.

(defun reverse* (list)
(let ((acc ()))
(dolist (item list acc)
(push item acc))))

The PUSH macro call is equivalent to (setf reversed (cons item
reversed)).

The loop has two variables. The explicit ACC that we set up for
accumulating the reversed list, as well as a hidden variable which
marches through the list, and sets up the value of ITEM on every
iteration.

The recursive version like Graham's is formed by visualizing each
iteration of the loop as a function. The loop variables become that
function's parameters, so that each iteration has its own ACC and its
own variable for accessing the next element in the list. That is to
say, under iteration, each iteration computes the new values of the
iteration variables and prepares the next values by directly assigning
to them, before branching back to the top of the loop. Under the
equivalent tail recursion, each ``iteration'' computes the new values
of the loop variables and then passes them as function arguments to
the next iteration, where they become the next iteration's variables.
The call simultaneously performs the role of the backward branch, and
the variable initialization.


.

Relevant Pages

  • Short koan-like code snippets (was: coerce for arbitrary types)
    ... (defun bfs6 (test children pending) ... The algorithm seems to be a tail-recursive expression of what ... I don't like using tail recursion to emulate iteration, ...
    (comp.lang.lisp)
  • Re: Iteration over recursion?
    ... I've been told that iteration in python is generally more ... More obvious (if you _have_ to use recursion) would be: ... in the inner loop too: ... d += delta ...
    (comp.lang.python)
  • Re: Ugly loop
    ... To me loop looks like a perfect solution to general iteration ... I think both iteration and recursion are natural in real-world ... programming and should be both be stressed for beginners. ...
    (comp.lang.lisp)
  • Re: Simple recursive functions in Lisp
    ... (if (null (cdr lst)) ... (labels ((rev (lst acc) ... becomes a loop variable. ... Another way to express Graham's algorithm is iteration. ...
    (comp.lang.lisp)
  • Re: Software bugs arent inevitable
    ... I suggested that for a given algorithm implemented ... iteration should always be faster by a small factor. ... > recursive function can run out of stack space while the heap still has ... Which is why, in the part you snipped, I said that recursion (unlike ...
    (comp.lang.python)