Path: news.media.mit.edu!bloom-beacon.mit.edu!xlink.net!howland.reston.ans.net!agate!cory.EECS.Berkeley.EDU!matt
From: matt@cory.EECS.Berkeley.EDU (Matt Wright)
Newsgroups: comp.lang.logo
Subject: Intuitive recursion
Date: 6 Jan 1994 20:26:54 GMT
Organization: University of California, Berkeley
Lines: 170
Message-ID: <2ghs6e$qe2@agate.berkeley.edu>
NNTP-Posting-Host: cory-138.eecs.berkeley.edu

Tommaso Russo asked me to post this to the newsgroup, since he can't do it
himself:

----------------------------cut here--------------------------------
Read in comp.lang.logo From: matt@volga.EECS.Berkeley.EDU (Matt Wright)

>...the approach is very informal and relies on the students getting an
>intuition.  (...)
>Now, I wouldn't want to try to teach recursion this way, 

Why not? See below.

>but I would hope to
>mix in the informal and the intuitive along with the more rigorous,
>mathematical type stuff. (...)
>Everything that I understand well about
>computer science I understand both on a formal level and on an informal
>level, and I think teachers should be able to (eventually) expect the same
>thing of their students. (...) - Matt

I agree completely.

Teaching recursion (true recursion, not just final one) has been a
puzzle for me for years. The most refractary student I had was my wife
(a math teacher that teach logo to mentally handicapped adults as part
of a therapy). Surprisly, the most receptive were university students
interested in fortran and already do-loop minded (yes, recursive
fortan exists!) for applications like quicksort and adaptive
quadrature. I realized that the main problem was not logical
difficulty, but rather NEED. Fortan students feel the need for
implementing a fast sort routine, and so appreciate the quicksort
algorithm and the recursive feature of a language. Children (and my
wife) do not feel the need for solving hanoi puzzles or exploring a
tree.

>From where, at a very low level, a need for recursion can arise? The
best answer I found up to now is from the need for TRANSPARENCY.
Transparent graphic procedures (i.e. those that leave the turtle in
exactly the same state it was) are higly appreciated as soon as one
realizes that they can be inserted in and deleted from a
superprocedure at will. Unfortunately, the way in wich transparency is
usually introduced, e.g.

to square :l 
fd :l rt 90 fd :l rt 90 fd :l rt 90 fd :l 
RT 90            ; do not forget, though it seems unnecessary!

is a good introduction to the turtle's theorem, not to recursion
(using REPEAT is even worse, since in this case one can think that the
last rt 90 is executed just because the teacher is too lazy to
distinguish between the firts three sides and the last).  This kinds
of procedures highlight the fact that the final heading of the turtle
must remain the same, but shadow the even more important fact that
this must be true also for its position.

I have developed the following stategy to raise the need for recursion:

My starting point: let's paint a sun. The turtle shall run on a circle
and, times to times, paint a ray. A ray is just a line, so, let's
write a procedure for a line:

to line :l 
fd :l

Not good, you have just renamed forward, and, more important, when the
ray has been painted, the turtle is far from the sun's surface. Return
back!

to tline :l 
fd :l bk :l

(somebody can write fd :l rt 180 fd :l, and this is a good place where
to point out that also the heading must return to its initial state.
Somebody adds now lt 180 (rather than rt 180), and this is also a good
starting point for the turtle's theorem). Ray is a natural extension:

to ray :l
lt 90 tline :l rt 90

sun is now easily made (maybe with internal rather than external rays,
but this is an easy-to-fix bug) and the concept of simmetry between
commands that do the job and commands for housekeeping starts to form.
A way to consolidate it is the VI procedure from Papert, written as

to vi :l
rt 45 tline :l lt 45
lt 45 tline :l rt 45

(note that lt 45 lt 45 should not be combined in lt 90: this would
hide the simmetry. The first lt 45 is housekeeping, the second one
starts another job. Somebody will do this, but this will be a result
of his/her reasoning)

or a centered line:

to cline :l
fd :l/2 bk :l/2
bk :l/2 fd :l/2

(same note).

The simmetry in these examples arises because we are painting forward
and backward open paths, not closed curves. To regard repeat 4[fd 100
rt 90] as a transparent procedure requires additional concepts: the
turtle's theorem and the closeness (right english?) of the path. (Both
would fail on a curve surface, and are difficult to handle in 3D).

The next step is another issue: iteration:

to polyspi :l :step :angle
fd :l :rt :ang
polyspi :l+:step :step :angle

(notice the + sign).

The autoreference of polyspi can be surprising, but is normally
accepted as "repeat the command with different arguments". This is
time to let people play exploring the polyspi microworld, appreciating
the different power of the arguments and leaving two more needs arise.

The first one comes from the annoying need of stopping the procedure
manually: let it stop automatically! Inserting a stop condition is
quite natural:

to polyspi :l :step :angle :max
if :l > :max [stop]
fd :l rt :angle
polyspi :l+:step :step :angle :max

(a decreasing spiral would not require the additional :max argument,
but if not stopped in time needs more explanation about negative numbers).

The second one comes from the need of typing cs after each try.  Most
attempt two consecutive polyspi commands, obtaining fine paints, but
not, as expected, two spirals superimposed and hence comparable.  They
realize and complain that polyspi is not transparent.

The solution must be given: having understood final recursion as
"iteration", nobody will guess that other commands can be executed by
polyspi after its final recursive ("iterative") call:

to polyspi :l :step :ang :max
if :l > :max [stop]
fd :l rt :ang
polyspi :l+:step :step :ang :max
lt :ang bk :l

This IS surprising: however, it works, and, what is more, shows the
already known symmetric structure of ray and vi: command-transparent
procedure-housekeeping. The need now arises for understanding WHY this
works: and this is time for the methaphores about the empeeror, his
servant, his servant's servant and so on.

(having used + rather than - in polyspi makes its results nearly
centered on the initial and final turtle's position an hence allows
for using it in paintings as flowers, fires etc.).

May be this helps somebody: however this is not completely
satisfactory to me, because to introduce recursion as final recursion
and explaining it as iteration is somehow misleading, thought it can
prepare the surprise needed to wonder seeing later a true recursive
call, feeling so the need for an insight in its structure. If somebody
else has developed a different strategy that works, I would like very
much to know it. Thanks.

                                            Tommaso Russo
                                        Russo@Area.Trieste.It