(defun uncompress (lst)
  (if (null lst)
      nil
      (let ((elt (car lst))
            (rest (uncompress (cdr lst))))
        (if (consp elt)
            (append (apply #'list-of elt)
                    rest)
            (cons elt rest)))))

(defun list-of (n elt)
  (if (zerop n)
      nil
      (cons elt (list-of (- n 1) elt))))

Can someone explain how calling uncompress inside of uncompress' let statement
works? Example usage of the uncompress function is as follows:

(uncompress '((3 1) 0 (2 1) 0))
(1 1 1 0 1 1 0)

  Pardon me, but this made me laugh out loud.  All that work by the Scheme
  freaks to teach people recursion and to abuse it for iteration, and the
  end result is that someone does not get it except for iteration!  It had
  to happen.  Nothing personal, Travis, this is your teachers' fault.

| Can someone explain how calling uncompress inside of uncompress' let
| statement works?

  Exactly like calling from somewhere else.  But watch the arguments.  The
  recursive call causes the tail to be processed before the head.  This
  means that when you call (uncompress '((3 1) (2 0))), the first thing it
  does is compute (uncompress '((2 0))), which yields (0 0) by prepending a
  list of two 0's to the empty list.  Then the rest of the first call takes
  control and prepends a list of three 1's to the tail it computed first,
  (0 0), and you get (1 1 1 0 0).  

  The smart thing about this solution is that it avoids copying the list it
  has already constructed.  That is indeed a good algorithm, but if one is
  concerned about wasted resources, reversing the list first does exactly
  the same good without the cost of the recursion.

--
Erik Naggum, Oslo, Norway

    (cons elt (list-of ... ...))

OK. list-of gets called recursively and returns a result which Lisp
silently puts someplace safe (the stack). Then cons gets called with elt
and the recursive result. Note that, just as with uncompress, the
temporary recursive result is indeed /computed/, but unlike uncompress
it is not /bound/ to a lexical variable you can look at in the source.

The only thing different with uncompress is that the programmer stashes
the recursive result (no diffence in the recursion per se) in the temp
variable rest, then looks at the type of the elt to see how that should
be processed. In both cases, consp and not, they pass the recursive
result to another function (here append or cons) for inclusion in the
net result.

Exercise: rewrite uncompress so it ends lexically with the recursive call.

You learn to understand recursive functions this way:  Start with
recursive functions where you already know what they do.  When you are
reasonably comfortable with that, you'll know how to think about them
and understanding new ones won't be hard either.

In this case, we already know what uncompress is supposed to do:
Given a list of elements x_1, ..., x_n, return a new list where each
of the x_i is replaced either by x_i itself, if x_i is a number, and
by x occurrences of k, if x_i is a list of the form (x k).

What you do now is prove, by induction on the length n of the input
list, that this implementation of UNCOMPRESS does in fact do this.

First we have to show that uncompress works for a list with n = 0
elements.  It obviously does.  Now just /assume/ that uncompress works
with input lists of length less than n.  We'll show that it works for
lists of length n, too, then, which means that, by induction,
UNCOMPRESS works for all lists (that are legal input).

Note also that this is a rather bad way of implementing such a
function.  Consider rewriting it with MAPCAN or LOOP (or both).

Regards,
--
Nils Goesche
"Don't ask for whom the <CTRL-G> tolls."

fun length nil   = 0
|   length(h::t) = 1 + length(t);

Things like that are very easy to understand so, until now, I have simply
viewed recursion as an elegant way to interate. I've never tried Scheme(I
like fast languages), and I've never spoken with a "Scheme freak"... In the
ANSI CL book, it says that you shouldn't attempt to trace through a recursive
function; however, the SML tutorial does exactly that. Is this the wrong way of
going about things? Maybe it's the nature of functional programming that just
as you feel everything is starting to click, you're back at square one...

  Damn.  I really thought I had something I could whack the Scheme freaks
  with this time.

| I have been programming imperatively for a good while, and I've always
| avoided recursion mainly because I found it confusing.

  Do you find function calls confusing?  Why?

| I've never tried Scheme (I like fast languages),

  I see.  This tells me that you are too quick to judge and do not pay
  attention to the details that would encourage you to look for better
  conclusions after the first one you reached has failed to produce the
  expected or desired results.

| Maybe it's the nature of functional programming that just as you feel
| everything is starting to click, you're back at square one...

  No, that would only be the nature of not getting the point.

  You need to become more comfortable with not understanding something
  before you can learn it well enough to understand it.  There is a very
  strong sense of rushing to conclusions in the way you speak of your
  problems and your approaches to learning something.  Acquire patience.

--
Erik Naggum, Oslo, Norway

Here is the tail recursive way:

(defun hello (n)
  (format t "~&Printing Hello ~A times." n)
  (labels ((print-times (k)
             (when (plusp k)
               (format t "~&Hello ~A!" (1+ (- n k)))
               (print-times (1- k)))))
    (print-times n))
  (format t "~&Done."))

And here the iterative way:

(defun hello (n)
  (format t "~&Printing Hello ~A times." n)
  (loop for k from 1 to n do
        (format t "~&Hello ~A!" k))
  (format t "~&Done."))

The iterative way looks much easier, in fact, and this example is
rather typical.  The reason functional programming freaks prefer the
recursive way, anyway, is that the iterative version uses assignment:
First, "Hello" is printed with k being 1, then k is reassigned to 2,
and so on (this is hidden by the LOOP macro, here).  In the recursive
version no such thing happens; print-times called with a different
argument each time instead.

And it is for this rather theoretical reason, that functional
programming freaks think it is ``cleaner'' to iterate using recursion,
even if the code looks much messier.

If you think this is a rather crazy attitude, then you are right: It
is.  In fact, people who use SML or Scheme know that taking the
functional programming paradigm too far isn't a good thing (otherwise
they'd be using Haskell instead, where in order to write even a simple
function like our HELLO above, you'd have to introduce an esoteric
thing called a ``monad''!), but somehow many of them still have
something like a ``bad conscience'' whenever they use assignment and
thus try to avoid loops.  Lispers are a rather more practical people:
They recognize that loops and tail recursion are equivalent, anyway,
and use whatever is easier for the case at hand.

Regards,
--
Nils Goesche
"Don't ask for whom the <CTRL-G> tolls."

  It is the first time in this newsgroup, but I have heard from people who
  have taken Scheme courses various places who actually think recursion is
  merely a form of iteration.  It would be silly to just claim this without
  some evidence, but nobody has wanted to come forward to admit it when
  they suspected the consequences or even grew the prerequisite clue.

  Teaching iteration as a form of recursion is just plain wrong as people
  get it backward: recursion is a form of iteration.  It sounds too silly to
  be believable, but ask around, and more than our unwitting contributor
  here will effectively say this.  I blame this squarely on stupid teaching
  methods and silly languages that teach the wrong thing to people who are
  a little too eager to jump to conclusions.  But those people /abound/ and
  it is the responsibility of teachers /not/ to send their students across
  mine fields to sort them out the hard way.

  I think teaching tail recursion as something separate from recursion is a
  really bad thing.  If you cannot deal with reality when you want to teach
  iteration, send your students to a class on theatrical make-up and ask
  them to come back to you when they understand the difference between
  staged make-believe and the real story.

--
Erik Naggum, Oslo, Norway

(defun length (list)
  (if (null list)
      0
      (let ((tail-length (length (cdr list))))
        (+ 1 tail-length))))

Recursion is only equivalent to iteration if you're returning the value of
the recursive call immediately, without doing anything to it.  A
tail-recursive LENGTH function might look like:

(defun length (list &optional (length-so-far 0))
  (if (null list)
      length-so-far
      (length (cdr list) (+ 1 length-so-far))))

Hi

many people have already answered you.

However, let me add a comment here.  There are algorithms that are
inherently recursive.

If you look at the code of the QuickSort algorithm or of Binary Tree
Traversal in *any* language, you will see that one of the (two in the
above cases) recursive calls is "in the middle".

You cannot eliminate this call, unless you explicitely manipulate a
stack.

Cheers

Regards,
--
Nils Goesche
"Don't ask for whom the <CTRL-G> tolls."

F(n) = F(n-1) + F(n-2)

This is difficult to express using tail recursion because you have to do
*two* recursive calls -- they can't *both* be the last thing you do.

Note: I didn't say it *can't* be done tail-recursively.  Any recursive
procedure can be transformed into a tail-recursive version, but the result
isn't always pretty because you have to pass the state around as parameters
rather than just stacking it up in the caller.  I haven't figured out what
the tail-recursive version of Fibonacci looks like (I think it would
involve two helper functions, one for the first subcall and the other for
the second subcall).

The first time I ever saw a QuickSort algorithm was in high school, I
hadn't done all that much programming and what I did was in brain
damaging languages.  The algorithm was implemented in FORTRAN.  It was
only 15-20 lines of code, but it took me hours to figure out what the
heck it was doing, and when I wanted to write a sort a month later, I
couldn't remember it.

A few years later, I saw it written recursively.  *bing*.  Why was this
so hard to understand before?

Michael

There's a fairly long discussion early on of what makes a function tail
recursive, and how to write functions so that they are tail recursive
when possible. It involves tracing through some functions to show what
happens to the stack with various kinds of recursion, and why tail
recursive functions can be optimized easily.

I found it informative (as someone who hadn't worked with lisp, scheme
or functional style for a dozen years).   I have to agree with you that
plain iteration is usually clearer in languages that support it. (Not
always though, once you're comfortable reading recursive code).  I think
there's some value in avoiding assignment, but that it is so miniscule
as not to matter when you have lexical scope and are dealing with a
variable that only lives through a few lines of simple code.

Michael

;-)

Regards,
--
Nils Goesche
Ask not for whom the <CONTROL-G> tolls.

Regards,
--
Nils Goesche
Ask not for whom the <CONTROL-G> tolls.

  I think `do´ is pretty strong as far as support for iteration goes.  At
  least it supports multi-variable sequential and parallel stepping, which
  is /far/ better than most of the languages that should have had good
  support for iteration because they are misdesigned as far as function
  calls are concerned, such as by not having multiple value return.

  However, when you encourage people to use recursion, the iteration
  support does not evolve.  People who tried to make improvements in the
  iteration department would be encouraged to use recursion, instead.

  Since recursion cannot evolve as a linguistic element, either, what you
  get is a stagnant language that requires more code and "patterns" to get
  things done.  E.g., collecting values while traversing a list.

  There are many ways to the same target, but finding the minimal set of
  operations necessary to accomplish it is far more important than whether
  you use an iterative or a tail-recursive or even recursive algorithm.  It
  appears to me that the focus on tail recursion forces people to play with
  loaded dice.

--
Erik Naggum, Oslo, Norway

Regards,
--
Nils Goesche
Ask not for whom the <CONTROL-G> tolls.