Is this what you want?
to square :side
repeat 4 [fd :side rt 90]
end
? penreverse
? repeat 10 [square 15*repcount wait 10 square 15*repcount]
--------------
People uninterested in the tail-recursion discussion can stop reading.
--------------
ti99_forever@[EMAIL PROTECTED]
writes:
>Even the first implementation of TI Logo back in 1979 had tail recursion.
>
>It is, of course, the simple form where the last line before the END
>is evaluated to see if a real procedure call with stack space is
>necessary
Many Logo implementations have had limited tail call elimination for
particular cases, as you describe. But this catches only the simplest
cases. In particular, very few Logo implementations have eliminated
tail calls in /operations/ -- Logo procedures that output values.
UCBLogo does tail call elimination in all cases. The tail call
elimination
itself isn't all that hard if you do it the way I do: by making IF, etc.,
be
macros, so that the conditionally-evaluated expression does end up in tail
position when it gets evaluated. The real difficulty, for me, anyway, has
been getting error handling to appear to the Logo user as if there were no
special handling of tail calls. The "XXX didn't output to YYY in ZZZ"
error
message is especially hard to get right. I think about 20% of the code in
UCBLogo's core evaluator could be eliminated if I were willing to have
users
see confusing values of XXX, YYY, and/or ZZZ under some cir***stances.
------
"Tail recursion" is /not/ the same idea as "iteration," especially when
you
think about operations. Consider this example:
to squares :numbers
if emptyp :numbers [output []]
output sentence (square first :numbers) (squares butfirst :numbers)
end
to square :num
output :num * :num
end
? show squares [7 10 3]
[49 100 9]
I would want to say that procedure SQUARES expresses an iteration -- it
goes
through a list of numbers, squaring each of them -- but it is /not/ tail
recursive. You can write SQUARES in a more complicated way that would be
tail
recursive, but it's not a way that anyone would naturally fall into using:
to squares :numbers [:result []]
if emptyp :numbers [output :result]
output (squares (butfirst :numbers)
(sentence :result (square first :numbers)))
end
(This version depends on the UCBLogo optional-input notation, but it could
be done in any Logo using a helper procedure.)
The moral of this is that "recursion" and "tail recursion" are names for a
specific programming technique (a procedure calling itself, and a
procedure
tail-calling itself, respectively), NOT names for a general
problem-solving
technique, such as "iteration," which means, more or less, doing the same
thing over and over.
My own taste is to prefer expressing iterations using higher-order
procedures,
as in this example:
to squares :numbers
output map [? * ?] :numbers
end
This isn't the most memory-efficient way to write it, but I claim it's the
easiest to read, and it makes the desired result easy to see.
The reason there is confusion about terminology is that other people don't
want to define "iteration" the way I do; they limit that name to
programming
techniques that run in constant memory. Only the tail-calling version of
SQUARES (the second one above, the one nobody but a computer scientist
would
write) is iterative by that definition.
So, there's room for disagreement about what "iteration" means, but I
think
that in the context of computer programming there's only one meaning for
"recursion," at least if you want other people to understand you.
And it's worth repeating the point that recursion is a much more general
technique than just to express iterations. Here's a great example from
Abelson and Sussman:
to count.change :amount :coins
if :amount = 0 [output 1]
if emptyp :coins [output 0]
if :amount < 0 [output 0]
output sum (count.change (:amount - first :coins) :coins) ~
(count.change :amount butfirst :coins)
end
This procedure outputs the number of different ways that a given amount of
money can be made up with coins of given denominations, e.g.,
? print count.change 15 [10 5 1]
6
because you can make 15 cents out of
- a dime and a nickel
- a dime and five pennies
- three nickels
- two nickels and five pennies
- a nickel and ten pennies
- 15 pennies
which make six different ways to do it.
This procedure can't possibly be understood as an iteration, by anyone's
definition. If you try, you'll get a headache. (I'm not saying that the
/problem/ couldn't be /solved/ using iteration, although it'd be much
harder that way.) You have to think of this as solving the problem by
recursively solving smaller subproblems:
to count.change :amount :coins
if :amount = 0 [output 1]
; There's only one way to make zero cents, namely with no coins!
if emptyp :coins [output 0]
; If the amount is nonzero, and you have no kinds of coins, you
; can't do it at all.
if :amount < 0 [output 0]
; If the amount of money you want is negative, you can't do it.
; (That may sound stupid, but it takes care of the case in which
; one of the coins is bigger than the amount we want, in which case
; using one of those coins leaves us with a negative amount left.)
output sum (count.change (:amount - first :coins) :coins) ~
(count.change :amount butfirst :coins)
; Otherwise, to solve the problem, you think: "Either I do or I
; don't use a coin of the first denomination. If I do, then I
; have accounted for FIRST :COINS cents, and so I have
; (:AMOUNT - FIRST :COINS) left to account for. I might use
; another coin of the same denomination for the remaining amount,
; so I should keep all of :COINS as possibilities. If I don't use
; a coin of the first denomination, then I still have :AMOUNT to
; deal with, and I have BUTFIRST :COINS as the possible coin sizes.
; The total number of ways to do it is the sum of the number of
; ways for each of the two cases.
end
|
