: > It will be hard enough to get this audience to believe that a garbage-
: > collected environment can possibly be fast enough, and that they needn't
: > worry about pointers and addresses any more, without trying to convince
: > them that they need to read wads of parentheses too.
I may be wrong but it is my own experience is that COND is the cause of a
lot of parenthesis errors and discomfort with novices. Starting them with
IF and WHEN should cut down on this considerably.
Also intro Lisp courses often reteach (or probably teach for the first
time) recursion and so novices get a extra dose of complexity. They
associate their frustration with the language rather than the content.
I noticed when playing around with Dylan I sure had to type a lot of
commas I never had to type in Lisp!
-David
In article <······················@129.105.100.185>,
·····@neves.ils.nwu.edu (David Neves) wrote:
> : > It will be hard enough to get this audience to believe that a garbage-
> : > collected environment can possibly be fast enough, and that they needn't
> : > worry about pointers and addresses any more, without trying to convince
> : > them that they need to read wads of parentheses too.
> I may be wrong but it is my own experience is that COND is the cause of a
> lot of parenthesis errors and discomfort with novices. Starting them with
> IF and WHEN should cut down on this considerably.
>
> Also intro Lisp courses often reteach (or probably teach for the first
> time) recursion and so novices get a extra dose of complexity. They
> associate their frustration with the language rather than the content.
The COND parenthesis problem completely disappears with a decent
parenthesis-oriented editor + pretty-printer. Once this is done,
students often find COND slightly more convenient, since dispatches
have more than 2 branches.
Re recursion: In my experience of teaching undergraduates, recursion is
far easier to teach and understand than iteration. The _only_ people who
had any problem with recursion were those who had had their brains damaged
(perhaps permanently) due to early exposure to Basic and/or assembly
language.
--
www/ftp directory:
ftp://ftp.netcom.com/pub/hb/hbaker/home.html
In article <·······················@192.0.2.1>, ······@netcom.com (Henry
Baker) wrote:
:
: The COND parenthesis problem completely disappears with a decent
: parenthesis-oriented editor + pretty-printer. Once this is done,
: students often find COND slightly more convenient, since dispatches
: have more than 2 branches.
I should have been more explicit. The COND problem is that it is counter
to most of Lisp (at least the part that novices see) where one sees a
single parenthesis in front of a function name. Since COND is taught so
early students get confused as to whether one or two parentheses should be
placed in front of a function name.
Possible errors:
(defun fact (x)
(cond (zerop x) 1
(t (* x (fact (1- x))))))
or
(defun fact (x)
(cond ((zerop x) 1)
((t (* x (fact (1- x))))))
IF is a lot more regular as you always see one parenthesis in front of a
function.
(defun fact (x)
(if (zerop x) 1 (* x (fact (1- x)))))
By the way, someone also mentioned DO and I also fault DO due to
parenthesis confusion. The iteration functions DOLIST and DOTIMES are
much easier for novices.
:
: Re recursion: In my experience of teaching undergraduates, recursion is
: far easier to teach and understand than iteration. The _only_ people who
: had any problem with recursion were those who had had their brains damaged
: (perhaps permanently) due to early exposure to Basic and/or assembly
: language.
I remember taking Lisp many years ago and trying to write a Union function
for class. The result was truly awful. I've never understood why
recursion is taught in Lisp -- other than the language (with its built in
list data type) makes it easier to try out recursion. Unfortunately
recursion usually isn't taught well enough in an intro class where
students are just trying to learn syntax.
The other problem with recursion in Lisp (for novices) is that it requires
knowledge of primitives that are counterintuitive to how lists look. The
primitives are CAR and CDR (or First and Rest). Visually lists looks kind
of like vectors -- any element should be reachable as quickly as any other
element. A student writing a MEMBER type function on a list might think
of using ELT. Writing recursion (for novices) is clearer in languages
like Pascal and C because the Record clearly defines (e.g. left-branch,
In article <·······················@192.0.2.1>, ······@netcom.com (Henry Baker) writes:
...
|> Re recursion: In my experience of teaching undergraduates, recursion is
|> far easier to teach and understand than iteration. The _only_ people who
|> had any problem with recursion were those who had had their brains damaged
|> (perhaps permanently) due to early exposure to Basic and/or assembly
|> language.
I beg to differ. Recursion is conceptually much more complex due to the
need to imagine multiple calls to a function INSIDE that function, with
different arguments. Getting the stopping condition right can be a pain.
(Though in truth I may have some lingering impairment from exposure to
Forth, FORTRAN, IDL, RTPL, C, Pascal, etc. :-))
I do think the syntax of DO is hard to remember, but it's conceptually
simple, and the LOOP macro makes most iteration trivial. Anyway, that has
been my experience.
Dan
In article <····················@den.mmc.com>, ·····@tigercat.den.mmc.com
(Dan Britt) wrote:
>I beg to differ. Recursion is conceptually much more complex due to the
>need to imagine multiple calls to a function INSIDE that function, with
>different arguments. Getting the stopping condition right can be a pain.
>(Though in truth I may have some lingering impairment from exposure to
>Forth, FORTRAN, IDL, RTPL, C, Pascal, etc. :-))
Years ago I had the pleasure of teaching Logo to children aged 9-15. The
lecture on recursion went very smoothly and everybody got the idea right
away. (Sorry, I don't remember how we presented it at this late date.)
On the other hand, I've had real trouble teaching recursion to many adults.
Chris
--
Chris Garrigues ···@DeepEddy.Com
609 Deep Eddy Avenue +1 512 499 0483
Austin, TX 78703-4513 USA
My pgp key is on my home page: http://www.DeepEddy.Com/~cwg/
In article <····················@den.mmc.com>, ·····@tigercat.den.mmc.com (Dan Britt) writes:
|> In article <·······················@192.0.2.1>, ······@netcom.com (Henry Baker) writes:
|> ...
|> |> Re recursion: In my experience of teaching undergraduates, recursion is
|> |> far easier to teach and understand than iteration. The _only_ people who
|> |> had any problem with recursion were those who had had their brains damaged
|> |> (perhaps permanently) due to early exposure to Basic and/or assembly
|> |> language.
|>
|> I beg to differ. Recursion is conceptually much more complex due to the
|> need to imagine multiple calls to a function INSIDE that function, with
|> different arguments. Getting the stopping condition right can be a pain.
|> (Though in truth I may have some lingering impairment from exposure to
|> Forth, FORTRAN, IDL, RTPL, C, Pascal, etc. :-))
Gee, I get to disagree with both of you! :-)
I disagree with Henry Baker in the cause of having problems with recursion.
In my not-so-humble opinion (I've been teaching CS since 1969), the reason
people have trouble with recursion lies in the way it is taught. Prior
knowledge of BASIC, much as I hate to admit it, is correlated with better
grades in introductory Pascal classes.
I disagree with Dan Britt that recursion is more complex than iteration.
But you are right -- if you need to imagine multiple calls to a function
INSIDE that function, then it IS very complex. And, unfortunately, that's
the way recursion is always taught.
I have a ten- or twelve-page paper on how to teach recursion the right way
which I wish I could post, but unfortunately it's not in machine-readable
form (I wrote it a long time ago). Here's a too-quick summary of one of
the main ideas:
When you write a function X that calls a function Y, you don't have to
step through function Y in order to determine whether function X is correct.
You just assume Y is correct (and check it separately, at some other time).
Thus you can debug X without worrying about Y. The trick in doing recursion
easily is to teach yourself to do this even when X = Y.
Sadly, every textbook that I know of teaches just the opposite: that to
understand recursion, you have to step through multiple levels. This is
Wrong.
-- ····@vfl.paramax.com -- If my header says otherwise, it lies.
In memoriam: The Space Age, 1969-1972.
····@gvls1.vfl.paramax.com (David Lee Matuszek) wrote:
> I disagree with Henry Baker in the cause of having problems with
> recursion. In my not-so-humble opinion (I've been teaching CS since
> 1969), the reason people have trouble with recursion lies in the way
> it is taught.
Several people teaching programming here at Rice agree with this and
with the methodology suggested by Mr. Matuszek; our own programming
courses use a similar viewpoint. Indeed, our very first course, which
is largely taught in Scheme, starts with recursion right from the
start, and our students seem to have little difficulty understanding
the notion.
To see some of our teaching materials, which are on-line, try
<A HREF="http://www.cs.rice.edu/~matthias/210web.html">Course</A>
Though we do not rely on any one text, we do make students work
through the book The Little Lisper (Friedman and Felleisen) in the
early part of the course.
'shriram
Shriram Krishnamurthi (·······@europa.cs.rice.edu) wrote:
> ····@gvls1.vfl.paramax.com (David Lee Matuszek) wrote:
> > I disagree with Henry Baker in the cause of having problems with
> > recursion. In my not-so-humble opinion (I've been teaching CS since
> > 1969), the reason people have trouble with recursion lies in the way
> > it is taught.
> Several people teaching programming here at Rice agree with this and
> with the methodology suggested by Mr. Matuszek; our own programming
> courses use a similar viewpoint. Indeed, our very first course, which
> is largely taught in Scheme, starts with recursion right from the
> start, and our students seem to have little difficulty understanding
> the notion.
The notion of recursion is clear and simple.
I feel it is sometimes more subtle deciding whether a particular *recursive
algorithm* does in fact produce the desired solution compared to an
iterative alternative.
> 'shriram
In article <··········@larry.rice.edu>,
Shriram Krishnamurthi <·······@europa.cs.rice.edu> wrote:
>
>Though we do not rely on any one text, we do make students work
>through the book The Little Lisper (Friedman and Felleisen) in the
>early part of the course.
>
Agreed: excellent book to teach from. ISBN 0-262-56038-0; published by
MIT Press in 1987. It teaches a very simple elegant functional LisP,
introduces recursion on page 15, and never bothers with iteration at
all. After all, if you can recurse, why iterate? spot the deliberate
flame bait :-}
Seriously though, it's short, light hearted, simple, direct and
effective. Works with kids as young as eight as well as with adults.
Try it (even if you've been writing in LisP for years).
--
------- ·····@rheged.dircon.co.uk (Simon Brooke)
;; When your hammer is C++, everything begins to look like a thumb.
From: Dave Yost
Subject: Re: Recursion where iteration would do
Date:
Message-ID: <3l25ju$2ns@Yost.com>
In article <·····················@VFL.Paramax.COM>,
David Lee Matuszek <····@gvls1.vfl.paramax.com> wrote:
>
>In my not-so-humble opinion (I've been teaching CS since 1969), the reason
>people have trouble with recursion lies in the way it is taught.
> ...
>When you write a function X that calls a function Y, you don't have to
>step through function Y in order to determine whether function X is correct.
>You just assume Y is correct (and check it separately, at some other time).
>Thus you can debug X without worrying about Y. The trick in doing recursion
>easily is to teach yourself to do this even when X = Y.
>
>Sadly, every textbook that I know of teaches just the opposite: that to
>understand recursion, you have to step through multiple levels. This is
>Wrong.
Using recursion when iteration would do has always bothered me.
I think it has something to do with this:
* iteration is simple in that it can only work linearly
(unless you muck it up with sufficient conditional code)
* recursion is more powerful (and therefore less simple) in that
it can iterate over more complex structures (trees, for example)
Therefore iteration-style code offers prima facie information
about its level of complexity.
When I look at iteration code, I know right away not to expect
anything more complex than a simple linear iteration. When I
look at recursive code, I have to examine it to determine if it's
a trivial case of linear iteration of if it's doing something
more complex. It's sort of like when someone tells you a joke
that has a big setup but an inane punch line. Your mind races
trying to imagine a complex resolution to the story, only to find
that most of the clues were red herrings distracting you from the
obvious, simple punch line. It leaves one feeling led on.
When the subject is a program, it's not just a matter of being
led on, it's a matter of unnecessary cognitive load. I've found
that some programmers love gratuitous cognitive load. Some don't.
I'm firmly in the latter camp. I prefer code that uses the
simplest construct available for each task, and when I see a more
complex construct than it seems like the task should take, it
leads me to try to figure out what it is about the task that I
must not understand yet that would have led the programmer to use
the more complex construct. An extremely simple example of what
I'm talking about is the use of "if" in lisp when there is no
"else" part. This leads one to look for the "else" part, then
note that there isn't one. If the programmer had used "when",
the extra wasted work would have been obviated.
This is part of a larger discussion about cognitive styles, perhaps.
Dave Yost
@ .com
····@Yost.com (Dave Yost) writes:
>David Lee Matuszek <····@gvls1.vfl.paramax.com> wrote:
>>Sadly, every textbook that I know of teaches just the opposite: that to
>>understand recursion, you have to step through multiple levels. This is
>>Wrong.
>
>Using recursion when iteration would do has always bothered me...
>When I look at iteration code, I know right away not to expect
>anything more complex than a simple linear iteration.
In _Simply Scheme_, we take pains to teach that in understanding a recursion
one should take the lower levels on faith.
Since beginners often find this mysterious, we introduce the idea by first
artificially writing the one recursive procedure
(define (foo L) (... (foo (cdr L)) ...))
as several separate procedures, one for each size argument:
(define (foo5 L) (... (foo4 (cdr L)) ...))
but working up from the base case. This means that at each step, everything
is firmly grounded in things we already know to work. Then we observe that
all but one of the foo_n procedures are identical, and this leads us to the
recursive form.
Once the students are convinced, by this bottom-up method, that the
self-referential foo makes sense, we teach them that in practice they can
and should write it directly, instead of going through the numbered versions
first. But if they get scared about the self-reference, they should imagine
that they are doing the numbered form.
We do also have a chapter called "How Recursion Works" in which we trace
through different levels, to clarify the point that local variables are
local to an invocation, not merely local to a procedure; that's the main
technical stumbling block, I think.
As for iteration and recursion, we introduce a wide range of higher-order
functions to handle iterative problems before we even mention recursion.
We do encourage the learner to use higher-order functions instead of
recursion when possible.
In article <··········@agate.berkeley.edu>, ··@anarres.CS.Berkeley.EDU
(Brian Harvey) wrote:
> ····@Yost.com (Dave Yost) writes:
> >David Lee Matuszek <····@gvls1.vfl.paramax.com> wrote:
> >>Sadly, every textbook that I know of teaches just the opposite: that to
> >>understand recursion, you have to step through multiple levels. This is
> >>Wrong.
> >
> >Using recursion when iteration would do has always bothered me...
> >When I look at iteration code, I know right away not to expect
> >anything more complex than a simple linear iteration.
>
> In _Simply Scheme_, we take pains to teach that in understanding a recursion
> one should take the lower levels on faith.
>
> Since beginners often find this mysterious, we introduce the idea by first
> artificially writing the one recursive procedure
> (define (foo L) (... (foo (cdr L)) ...))
> as several separate procedures, one for each size argument:
> (define (foo5 L) (... (foo4 (cdr L)) ...))
> but working up from the base case. This means that at each step, everything
> is firmly grounded in things we already know to work. Then we observe that
> all but one of the foo_n procedures are identical, and this leads us to the
> recursive form.
This is a very good approach for budding Computer Scientists.
The nice thing about this teaching technique is that it leads directly
to an understanding of the Y combinator and the 'least-fixed-point' lattice
theory of approximations to functions.
E.g., the Y combinator lazily produces foo5 'just-in-time' when foo5 is
required.
(See ftp://ftp.netcom.com/pub/hb/hbaker/ForthStack.html & .ps.Z for more
about Y combinators.)
The continuous functional approach shows that the recursive function is
the mathematical limit of foo1, foo2, foo3, ...
--
www/ftp directory:
ftp://ftp.netcom.com/pub/hb/hbaker/home.html
Dave Yost (····@Yost.com) wrote:
> When I look at iteration code, I know right away not to expect
> anything more complex than a simple linear iteration. When I
> look at recursive code, I have to examine it to determine if it's
> a trivial case of linear iteration of if it's doing something
> more complex. It's sort of like when someone tells you a joke
But analysis of our programs/algorithms is always a useful exercise
even in the case of simple programs. In teaching introductory
students I have experimented with having students explicitly
write out the continuation of each recursive call to a fn
as (lambda (z) ...). Tail recursive functions are easily
identified when each continuation is the identity function.
Moreover, students quickly discover that the computation can
be written as a linear sequence of compositions of these
continuation functions. Once this is done for few cases, students
begin to recognize the oft repeated recursive constructs as
an idiom of expression for the linear sequences of functional
compositions the represent.
--
________________________________________________________________________
John E. Howland internet: ········@ariel.cs.trinity.edu
Computer Science Department telephone: (210) 736-7480
Trinity University fax: (210) 736-7477
In article <··········@tusol.cs.trinity.edu>,
········@ariel.cs.trinity.edu (John E. Howland) wrote:
> I have experimented with having students explicitly
> write out the continuation of each recursive call to a fn
> as (lambda (z) ...). Tail recursive functions are easily
> identified when each continuation is the identity function.
Don't you mean that the continuation is _eta-reducible_ -- i.e.,
the continuation is (lambda (x) (c x)), where c is the continuation
function -- in the case of a tail-recursive call???
--
www/ftp directory:
ftp://ftp.netcom.com/pub/hb/hbaker/home.html
In article <··········@Yost.com> ····@Yost.com (Dave Yost) writes:
>Using recursion when iteration would do has always bothered me.
>
>I think it has something to do with this:
> * iteration is simple in that it can only work linearly
> (unless you muck it up with sufficient conditional code)
> * recursion is more powerful (and therefore less simple) in that
> it can iterate over more complex structures (trees, for example)
>Therefore iteration-style code offers prima facie information
>about its level of complexity.
There's some truth to this, especially in Common Lisp where the
compilers do not necessarily optimize tail recursion. On the other
hand, recursion sometimes has the advantage that it is easier to come
back later and add some cases. For instance, consider a naive
factorial-like implementation of exponentiation:
(defun Power (Base Exponent)
"Reproduce EXPT in case where Exponent is non-negative integer"
(cond
((= Exponent 0) 1)
(t (* Base (Power Base (- Exponent 1))))) )
Now, this is no simpler than the looping algorithm. However, when you
notice that X^N can be expressed as (X^2)^(N/2), one additional case
converts the O(N) algorithm to the O(lg N) one below:
(defun Power (Base Exponent)
"Reproduce EXPT in case where Exponent is non-negative integer"
(cond
((= Exponent 0) 1)
((evenp Exponent)(Power (* Base Base) (/ Exponent 2)))
(t (* Base (Power Base (- Exponent 1))))) )
Converting the looping algorithm into one that does repeated squaring
is quite a bit harder, IMHO.
Anecdotes like this prove nothing, of course. However, it has been my
personal experience that recursive algorithms are a bit more likely to
be extensible. In addition, as a purely practical matter, TRACE and
the debugger give more information about recursive algorithms than
iterative ones.
I guess the point is that everyone needs to be comfortable with both
approaches, and anybody who can only do one or the other is
ill-equipped. I'm certainly not advocating that algorithms always (or
nearly always) be expressed recursively.
- Marty
(proclaim '(inline skates))
You might be surprised to learn that repeated squaring is not
always more efficient than multiplication when computing powers
(e.g. this is the case when computing powers of polynomials,
see Richard Fateman's thesis, or any good text on computer
algebra).
In general, one would need very powerful algorithm analysis
tools to automatically decide which powering method is more
efficient in a particular monoid.
-Bill
In article <·····················@VFL.Paramax.COM>,
····@gvls1.vfl.paramax.com (David Lee Matuszek) wrote:
> In article <····················@den.mmc.com>,
·····@tigercat.den.mmc.com (Dan Britt) writes:
> |> In article <·······················@192.0.2.1>, ······@netcom.com
(Henry Baker) writes:
> |> ...
> |> |> Re recursion: In my experience of teaching undergraduates, recursion is
> |> |> far easier to teach and understand than iteration. The _only_
people who
> |> |> had any problem with recursion were those who had had their brains
damaged
> |> |> (perhaps permanently) due to early exposure to Basic and/or assembly
> |> |> language.
> |>
> |> I beg to differ. Recursion is conceptually much more complex due to the
> |> need to imagine multiple calls to a function INSIDE that function, with
> |> different arguments. Getting the stopping condition right can be a pain.
> |> (Though in truth I may have some lingering impairment from exposure to
> |> Forth, FORTRAN, IDL, RTPL, C, Pascal, etc. :-))
>
> Gee, I get to disagree with both of you! :-)
>
> I disagree with Henry Baker in the cause of having problems with recursion.
> In my not-so-humble opinion (I've been teaching CS since 1969), the reason
> people have trouble with recursion lies in the way it is taught. Prior
> knowledge of BASIC, much as I hate to admit it, is correlated with better
> grades in introductory Pascal classes.
I don't doubt it, since Pascal prefers iteration over recursion. Also, the
non-interactive nature of Pascal makes the students unbelievably
conservative, because they have a finite amount of time in which to
do their homework. With interactive Lisp and APL, on the other hand, the
students can play with a few examples, and quickly reach an understanding.
My experience stems from teaching Lisp, Pascal and APL. Interestingly
enough, the _computer science_ undergraduates (usually the ones with
previous assembler and/or BASIC experience) were the ones having great
difficulty with recursion. The pre-med, pre-law, physics and chemistry
students did just fine (not at all what I would have guessed in advance).
Go figure.
--
www/ftp directory:
ftp://ftp.netcom.com/pub/hb/hbaker/home.html
In article <····················@den.mmc.com> ·····@tigercat.den.mmc.com (Dan Britt) writes:
|> ... The _only_ people who
|> had any problem with recursion were those who had had their brains damaged
|> (perhaps permanently) due to early exposure to Basic and/or assembly
|> language.
I beg to differ. Recursion is conceptually much more complex due to the
need to imagine multiple calls to a function INSIDE that function, with
different arguments.
wow....
if you think of recursion that way i can see why you think it is hard.
i think you are making a case that early exposure to basic on the part
of the *teacher* is what makes recursion hard to learn.
In article <·················@hellespont.crl.nmsu.edu>, ···@crl.nmsu.edu
(Ted Dunning) wrote:
> if you think of recursion that way i can see why you think it is hard.
Recursion as taught in a traditional introductory Computer Science course
(say, taught using Pascal) is usually a later topic, and it is hard to
grasp when done using Pascal. I think part of the reason is the use of
VAR and non-VAR parameters in Pascal. Students use VAR parameters all over
the place. Pascal also allows functions/procedures to be declared inside
others, and it is difficult at the outset to separate that concept
(*lexical* scoping) from the idea of a function calling itself. I recall
early on in a class not understanding how a recursive function defined
inside another function's scope could still call top-level functions - I
didn't grasp why once the function had called itself several times, it
could still "see" the top-level functions. I was jumbling up a whole
slew of ideas here: lexical scope was getting confused with the function's
executing context.
When you've already got the confusing topics of nested functions and
passing parameters by value vs. Pascal's VAR, then recursion doesn't
really make sense until you understand stack frames. Stack frames are
a machine-level concept. (Even if compilers now often pass parameters
via registers instead, the stack is still the concept taught).
In Lisp or Scheme, recursive thinking is taught immediately. It is the
whole point of the book "The Little Lisper." In Lisp, you start out
by thinking of functions as being more like mathematical functions.
You don't have the notion of pointers (at least, not early on). The
concept of lexical scopes or "closures" is more important, so that is
learned as a distinct concept as well.
So I guess I can say that after a basic education in Computer Science
taught entirely using Pascal and assembly language, I had little concept
of recursion's real usability. I did write a Knight's Tour solver in
Pascal, but such a program is much uglier in Pascal than it is in a
language like Scheme. I didn't really understand how useful recursion
could be until I started looking at NewtonScript, Scheme, and Dylan.
And I still don't often jump to a recursive solution.
Another reason: in Pascal, C, and C++, and especially under Windows
where the stack comes out of what's left of your 64K DGROUP segment,
recursion generally means a stack overflow. That's another reason why
programmers learn to fear rather than value recursion.
-Paul-
--
Paul R. Potts - Software Engineer - Fry Multimedia
······@frymulti.com - http://frymulti.com/~ppotts