The old Google Groups will be going away soon, but your browser is incompatible with the new version.
This is a Usenet group - learn more
Midfunction Recursion
 There are currently too many topics in this group that display first. To make this topic appear first, remove this option from another topic. There was an error processing your request. Please try again. Standard view   View as tree
 Messages 1 - 25 of 67 Newer >
The group you are posting to is a Usenet group. Messages posted to this group will make your email address visible to anyone on the Internet.
Your reply message has not been sent.
Your post was successful

From:
To:
Cc:
Followup To:
 Add Cc | Add Followup-to | Edit Subject
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Oct 23 2002, 11:09 am
Newsgroups: comp.lang.lisp
From: Travis Whitton <whit...@atlantic.net>
Date: Wed, 23 Oct 2002 14:59:12 GMT
Local: Wed, Oct 23 2002 10:59 am
Subject: Midfunction Recursion
Hello, I'm steadily working my way through Paul Graham's ANSI Common Lisp,
and I've come to something that I don't quite understand. While I don't have
any problem understanding recursive functions where the function call is
the last statement in the function, this particular function calls itself
in the middle, and I can't rationalize exactly how it works.

(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)

Travis Whitton <whit...@atlantic.net>

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Oct 23 2002, 11:31 am
Newsgroups: comp.lang.lisp
From: Erik Naggum <e...@naggum.no>
Date: 23 Oct 2002 15:31:57 +0000
Local: Wed, Oct 23 2002 11:31 am
Subject: Re: Midfunction Recursion
* Travis Whitton
| While I don't have any problem understanding recursive functions where
| the function call is the last statement in the function, this particular
| function calls itself in the middle, and I can't rationalize exactly how
| it works.

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

Act from reason, and failure makes you rethink and study harder.
Act from faith, and failure makes you blame someone and push harder.

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Oct 23 2002, 11:46 am
Newsgroups: comp.lang.lisp
From: Kenny Tilton <ktil...@nyc.rr.com>
Date: Wed, 23 Oct 2002 15:42:43 GMT
Local: Wed, Oct 23 2002 11:42 am
Subject: Re: Midfunction Recursion

Travis Whitton wrote:
> Hello, I'm steadily working my way through Paul Graham's ANSI Common Lisp,
> and I've come to something that I don't quite understand. While I don't have
> any problem understanding recursive functions where the function call is
> the last statement in the function, this particular function calls itself
> in the middle, and I can't rationalize exactly how it works.

The function list-of does the kind of recursion with which you are
comfortable, yes? Where the last form is:

(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.

--

kenny tilton
clinisys, inc
---------------------------------------------------------------
""Well, I've wrestled with reality for thirty-five years, Doctor,
and I'm happy to state I finally won out over it.""
Elwood P. Dowd

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Oct 23 2002, 11:49 am
Newsgroups: comp.lang.lisp
From: Nils Goesche <car...@cartan.de>
Date: 23 Oct 2002 17:49:15 +0200
Local: Wed, Oct 23 2002 11:49 am
Subject: Re: Midfunction Recursion

Travis Whitton <whit...@atlantic.net> writes:
> Hello, I'm steadily working my way through Paul Graham's ANSI Common
> Lisp, and I've come to something that I don't quite
> understand. While I don't have any problem understanding recursive
> functions where the function call is the last statement in the
> function, this particular function calls itself in the middle, and I
> can't rationalize exactly how it works.

Is this really code from ANSI Common Lisp?  It looks like being
written by a Schemer...

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).

> (defun uncompress (list) ; Unlike Scheme, in Lisp you can call a
>                          ; list a list
>   (if (null list)
>       nil
>       (let ((elt (car list))
>             (rest (uncompress (cdr list))))

Note here that (cdr list) contains a (legal) list of length n - 1, and
we already know, by assumption, that uncompress works for such lists.
So, REST now contains the correct expansion of (cdr list).  Now read
the rest of the code and you'll see that it works for our list LIST of
length n, too, QED.

This is how you understand recursive functions: You do /not/ try to
follow the call chain, you simply prove, by induction, that they work.
As you have seen, for the most part this means that you can simply
assume that the function already works (for smaller input at least),
which makes things usually very easy.

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."

PGP key ID 0x0655CFA0

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Oct 23 2002, 12:12 pm
Newsgroups: comp.lang.lisp
From: Jacek Generowicz <jacek.generow...@cern.ch>
Date: 23 Oct 2002 17:49:54 +0200
Local: Wed, Oct 23 2002 11:49 am
Subject: Re: Midfunction Recursion

Travis Whitton <whit...@atlantic.net> writes:
> While I don't have any problem understanding recursive functions
> where the function call is the last statement in the function, this
> particular function calls itself in the middle, and I can't
> rationalize exactly how it works.

Calling itself at the end (tail-recursion) allows you to re-express
the recursive function as a loop, but that is not how recursion works
in general.

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

Just like calling any other function inside the let statement would
work. You push onto the stack whatever data are necessary to pick up
execution of the function where it left off, and go off and run
whatever function you called. Typically the stack is piled high with
information about "half-completed" functions. You don't much care
about what appears in the stack below you: there is nothing to prevent
(information about half-completed states of) the same function
appearing in the stack more than once.

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Oct 23 2002, 12:19 pm
Newsgroups: comp.lang.lisp
From: Travis Whitton <whit...@atlantic.net>
Date: Wed, 23 Oct 2002 16:08:35 GMT
Local: Wed, Oct 23 2002 12:08 pm
Subject: Re: Midfunction Recursion

>   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.

Well... I'm teaching myself, so I guess it's my own fault. I'm trying to
expand my programming repertoire by learning a functional language. I have
been programming imperatively for a good while, and I've always avoided
recursion mainly because I found it confusing. I started off reading a gentle
introduction to SML, and almost all of it's examples use recursion to
iterate i.e.,

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...

-
Travis Whitton <whit...@atlantic.net>

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Oct 23 2002, 12:30 pm
Newsgroups: comp.lang.lisp
From: Travis Whitton <whit...@atlantic.net>
Date: Wed, 23 Oct 2002 16:19:41 GMT
Local: Wed, Oct 23 2002 12:19 pm
Subject: Re: Midfunction Recursion
Thanks to all of you for the help. I shall digest this information and
hopefully one day achieve recursive enlightenment.

-
Travis Whitton <whit...@atlantic.net>

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Oct 23 2002, 12:45 pm
Newsgroups: comp.lang.lisp
From: Erik Naggum <e...@naggum.no>
Date: 23 Oct 2002 16:41:00 +0000
Subject: Re: Midfunction Recursion
* Travis Whitton
| Well... I'm teaching myself, so I guess it's my own fault.

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

Act from reason, and failure makes you rethink and study harder.
Act from faith, and failure makes you blame someone and push harder.

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Oct 23 2002, 1:07 pm
Newsgroups: comp.lang.lisp
From: Nils Goesche <car...@cartan.de>
Date: 23 Oct 2002 19:06:58 +0200
Local: Wed, Oct 23 2002 1:06 pm
Subject: Re: Midfunction Recursion

Travis Whitton <whit...@atlantic.net> writes:
> > 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.

> Well... I'm teaching myself, so I guess it's my own fault.

Not really.  SML freaks are very similar to Scheme freaks in this
regard :-)

> I'm trying to expand my programming repertoire by learning a
> functional language. I have been programming imperatively for a good
> while, and I've always avoided recursion mainly because I found it
> confusing. I started off reading a gentle introduction to SML, and
> almost all of it's examples use recursion to iterate i.e.,

> 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.

Yes, tail recursion is easy to understand.  In fact, tail recursion is
equivalent to iteration, so there is no practical reason to prefer one
way to the other.  There is a theoretical difference, though.  Let's
write, for example, a function that prints Hello n times.

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.

> 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...

No, what you have to understand is when to be functional and when
rather not :-)

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

PGP key ID 0x0655CFA0

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Oct 23 2002, 1:34 pm
Newsgroups: comp.lang.lisp
From: Erik Naggum <e...@naggum.no>
Date: 23 Oct 2002 17:34:33 +0000
Local: Wed, Oct 23 2002 1:34 pm
Subject: Re: Midfunction Recursion
* Nils Goesche
| Yes, tail recursion is easy to understand.

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

Act from reason, and failure makes you rethink and study harder.
Act from faith, and failure makes you blame someone and push harder.

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Oct 23 2002, 1:48 pm
Newsgroups: comp.lang.lisp
From: Barry Margolin <bar...@genuity.net>
Date: Wed, 23 Oct 2002 17:48:00 GMT
Subject: Re: Midfunction Recursion
In article <slrnardivu.gnj.whit...@grub.atlantic.net>,
Travis Whitton  <whit...@atlantic.net> wrote:

>>   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.

>Well... I'm teaching myself, so I guess it's my own fault. I'm trying to
>expand my programming repertoire by learning a functional language. I have
>been programming imperatively for a good while, and I've always avoided
>recursion mainly because I found it confusing. I started off reading a gentle
>introduction to SML, and almost all of it's examples use recursion to
>iterate i.e.,

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

That's not tail recursion, it's recursing in the middle, which you claimed
not to understand.  It calls length() recursively, and *then* adds 1 to
that before returning.  An equivalent Lisp version would be:

(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))))

--
Barry Margolin, bar...@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Oct 23 2002, 1:59 pm
Newsgroups: comp.lang.lisp
From: Marco Antoniotti <marc...@cs.nyu.edu>
Date: 23 Oct 2002 14:01:35 -0400
Local: Wed, Oct 23 2002 2:01 pm
Subject: Re: Midfunction Recursion

Hi

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

--
Marco Antoniotti ========================================================
NYU Courant Bioinformatics Group        tel. +1 - 212 - 998 3488
715 Broadway 10th Floor                 fax  +1 - 212 - 995 4122
New York, NY 10003, USA                 http://bioinformatics.cat.nyu.edu
"Hello New York! We'll do what we can!"
Bill Murray in `Ghostbusters'.

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Oct 23 2002, 2:08 pm
Newsgroups: comp.lang.lisp
From: Nils Goesche <car...@cartan.de>
Date: 23 Oct 2002 20:08:45 +0200
Local: Wed, Oct 23 2002 2:08 pm
Subject: Re: Midfunction Recursion

Erik Naggum <e...@naggum.no> writes:
> * Nils Goesche
> | Yes, tail recursion is easy to understand.

>   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.
...
>   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.

Ugh!  I probably should have written ``Tail recursive code is easy to
understand for people who already understand recursion (in general)''.
It would have never occurred to me that there might be people who get
it wrong this way.  I guess this is because I heard of tail recursion
only many years after I understood recursion for the first time, when
I was still programming in Pascal.  But, obviously, the danger is
real...

>   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.
...
>   I think teaching tail recursion as something separate from
>   recursion is a really bad thing.

Yes, this is clear now.  I can't remember where I learned about tail
recursion, only that it was some Scheme text claiming that this was a
better way to write loops.  I'd like to look back whether they
properly explained recursion first... I think they didn't.  How about
SICP?  Do they treat general recursion first?  (I don't have my copy
handy at the moment)

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

PGP key ID 0x0655CFA0

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Oct 23 2002, 2:29 pm
Newsgroups: comp.lang.lisp
From: Barry Margolin <bar...@genuity.net>
Date: Wed, 23 Oct 2002 18:29:15 GMT
Local: Wed, Oct 23 2002 2:29 pm
Subject: Re: Midfunction Recursion
In article <y6csmyxkpa8....@octagon.valis.nyu.edu>,
Marco Antoniotti  <marc...@cs.nyu.edu> wrote:

>Hi

>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".

Another well-known example that uses mid-function recursion is the
Fibonacci number series:

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).

--
Barry Margolin, bar...@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Oct 23 2002, 4:07 pm
Newsgroups: comp.lang.lisp
From: Joe Marshall <j...@ccs.neu.edu>
Date: 23 Oct 2002 16:07:49 -0400
Local: Wed, Oct 23 2002 4:07 pm
Subject: Re: Midfunction Recursion

Nils Goesche <car...@cartan.de> writes:
> SICP?  Do they treat general recursion first?  (I don't have my copy
> handy at the moment)

It is presented simultaneously with general recursion.

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Oct 23 2002, 4:21 pm
Newsgroups: comp.lang.lisp
From: mich...@bcect.com (Michael Sullivan)
Date: Wed, 23 Oct 2002 15:51:50 -0400
Local: Wed, Oct 23 2002 3:51 pm
Subject: Re: Midfunction Recursion

Marco Antoniotti <marc...@cs.nyu.edu> wrote:
> 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.

And those are great examples of algorithms that should almost never be
written without recursion.

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

--
Michael Sullivan
Business Card Express of CT             Thermographers to the Trade
Cheshire, CT                                      mich...@bcect.com

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Oct 23 2002, 4:21 pm
Newsgroups: comp.lang.lisp
From: mich...@bcect.com (Michael Sullivan)
Date: Wed, 23 Oct 2002 15:51:49 -0400
Local: Wed, Oct 23 2002 3:51 pm
Subject: Re: Midfunction Recursion

Yes.  I don't have my copy handy either, but I read through that section
only a couple months ago, so I'm willing to talk from memory.  They do
get right into tail recursion in the same discussion.  I would have said
they take a reasonable attitude toward the subject, but they clearly
want students to try out the functional "freak" style of using tail
recursion in place of iteration. They don't imply that it's the be-all
and end-all, just that it's worth trying out for yourself, which seems
fair to me.

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

--
Michael Sullivan
Business Card Express of CT             Thermographers to the Trade
Cheshire, CT                                      mich...@bcect.com

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Oct 23 2002, 4:56 pm
Newsgroups: comp.lang.lisp
From: g...@jpl.nasa.gov (Erann Gat)
Date: Wed, 23 Oct 2002 13:10:53 -0700
Local: Wed, Oct 23 2002 4:10 pm
Subject: Re: Midfunction Recursion
In article <%TBt9.23\$9F6.2...@paloalto-snr1.gtei.net>, Barry Margolin

<bar...@genuity.net> wrote:
>  I haven't figured out what
> the tail-recursive version of Fibonacci looks like

(defun tail-fib (n &optional (n1 1) (n2 1))
(if (<= n 1) n1 (tail-fib (1- n) n2 (+ n1 n2))))

;-)

E.

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Oct 23 2002, 5:11 pm
Newsgroups: comp.lang.lisp
From: Kalle Olavi Niemitalo <k...@iki.fi>
Date: 23 Oct 2002 23:53:03 +0300
Local: Wed, Oct 23 2002 4:53 pm
Subject: Re: Midfunction Recursion

Barry Margolin <bar...@genuity.net> writes:
> 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).

(defun fib (x)
(labels ((helper (i fib-i-1 fib-i)
(if (>= i x)
fib-i
(helper (+ i 1) fib-i (+ fib-i-1 fib-i)))))
(helper 0 1 0)))

I suppose this is cheating.

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Oct 23 2002, 5:48 pm
Newsgroups: comp.lang.lisp
From: Nils Goesche <n...@cartan.de>
Date: 23 Oct 2002 23:48:07 +0200
Local: Wed, Oct 23 2002 5:48 pm
Subject: Re: Midfunction Recursion

mich...@bcect.com (Michael Sullivan) writes:
> Nils Goesche <car...@cartan.de> wrote:

> > How about SICP?  Do they treat general recursion first?  (I
> > don't have my copy handy at the moment)

> Yes.  I don't have my copy handy either, but I read through that section
> only a couple months ago, so I'm willing to talk from memory.  They do
> get right into tail recursion in the same discussion.  I would have said
> they take a reasonable attitude toward the subject, but they clearly
> want students to try out the functional "freak" style of using tail
> recursion in place of iteration. They don't imply that it's the be-all
> and end-all, just that it's worth trying out for yourself, which seems
> fair to me.

a while ago where it seemed that there are too many students who
get it wrong when it is done this way.

> I have to agree with you that plain iteration is usually
> clearer in languages that support it.

It has always been my impression that designers of languages
which don't support iteration sufficiently, like Scheme which has
only the awkward `do', do so quite deliberately in order to force
people into the tail recursive style.

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

PGP key ID #xD26EF2A0

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Oct 23 2002, 5:55 pm
Newsgroups: comp.lang.lisp
From: Barry Margolin <bar...@genuity.net>
Date: Wed, 23 Oct 2002 21:55:16 GMT
Local: Wed, Oct 23 2002 5:55 pm
Subject: Re: Midfunction Recursion
In article <87elagg73c....@darkstar.cartan>,
Nils Goesche  <n...@cartan.de> wrote:

>It has always been my impression that designers of languages
>which don't support iteration sufficiently, like Scheme which has
>only the awkward `do', do so quite deliberately in order to force
>people into the tail recursive style.

You have to remember that Scheme was designed to support the paradigms
espoused in all the "Lambda: The Ultimate XXX" papers.  The idea was that
function calls could be used as the basis for almost all control
structures.

--
Barry Margolin, bar...@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Oct 23 2002, 6:03 pm
Newsgroups: comp.lang.lisp
From: Nils Goesche <n...@cartan.de>
Date: 24 Oct 2002 00:03:09 +0200
Local: Wed, Oct 23 2002 6:03 pm
Subject: Re: Midfunction Recursion

Barry Margolin <bar...@genuity.net> writes:
> In article <87elagg73c....@darkstar.cartan>,
> Nils Goesche  <n...@cartan.de> wrote:
> >It has always been my impression that designers of languages
> >which don't support iteration sufficiently, like Scheme which has
> >only the awkward `do', do so quite deliberately in order to force
> >people into the tail recursive style.

> You have to remember that Scheme was designed to support the
> paradigms espoused in all the "Lambda: The Ultimate XXX"
> papers.  The idea was that function calls could be used as the
> basis for almost all control structures.

Hm, ok, but couldn't they have omitted `do' altogether, then?

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

PGP key ID #xD26EF2A0

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Oct 23 2002, 6:10 pm
Newsgroups: comp.lang.lisp
From: Barry Margolin <bar...@genuity.net>
Date: Wed, 23 Oct 2002 22:10:06 GMT
Local: Wed, Oct 23 2002 6:10 pm
Subject: Re: Midfunction Recursion
Nils Goesche  <n...@cartan.de> wrote:

>Barry Margolin <bar...@genuity.net> writes:

>> In article <87elagg73c....@darkstar.cartan>,
>> Nils Goesche  <n...@cartan.de> wrote:
>> >It has always been my impression that designers of languages
>> >which don't support iteration sufficiently, like Scheme which has
>> >only the awkward `do', do so quite deliberately in order to force
>> >people into the tail recursive style.

>> You have to remember that Scheme was designed to support the
>> paradigms espoused in all the "Lambda: The Ultimate XXX"
>> papers.  The idea was that function calls could be used as the
>> basis for almost all control structures.

>Hm, ok, but couldn't they have omitted `do' altogether, then?

Yes.  Over time a few "practical" features were added to the language, as
it gained more use outside the academic fold.

--
Barry Margolin, bar...@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Oct 23 2002, 6:11 pm
Newsgroups: comp.lang.lisp
From: Erik Naggum <e...@naggum.no>
Date: 23 Oct 2002 22:11:37 +0000
Local: Wed, Oct 23 2002 6:11 pm
Subject: Re: Midfunction Recursion
* Nils Goesche
| It has always been my impression that designers of languages which don't
| support iteration sufficiently, like Scheme which has only the awkward
| `do', do so quite deliberately in order to force people into the tail
| recursive style.

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

--
Erik Naggum, Oslo, Norway

Act from reason, and failure makes you rethink and study harder.
Act from faith, and failure makes you blame someone and push harder.

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Oct 23 2002, 6:42 pm
Newsgroups: comp.lang.lisp
From: Nils Goesche <n...@cartan.de>
Date: 24 Oct 2002 00:42:25 +0200
Local: Wed, Oct 23 2002 6:42 pm
Subject: Re: Midfunction Recursion

Erik Naggum <e...@naggum.no> writes:
> * Nils Goesche
> | It has always been my impression that designers of languages
> | which don't support iteration sufficiently, like Scheme which
> | has only the awkward `do', do so quite deliberately in order
> | to force people into the tail recursive style.

>   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.

Come to think of it, that's true: Some languages have only
`while' and a `for' that works only on fixnum intervals (and both
don't return a useful value).  Guess I was comparing it to LOOP :-)
But even though I always used DO until I discovered that LOOP
isn't that hard to understand, after all, I never really got used
to it -- I still think it is somewhat hard to read (unlike LOOP).

>   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

Heh.  Obviously there are people who think that submitting to a
certain ideology is far more important than to accomplish
anything...

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

PGP key ID #xD26EF2A0

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
 Messages 1 - 25 of 67 Newer >
 « Back to Discussions « Newer topic Older topic »