The message below is being cross-posted from the LogoForum. Please
reply here at comp.lang.logo and it will be cross-posted back to the
LogoForum. The original author of this message is
taobert@[EMAIL PROTECTED]
in Wikipedia about recursion :
Recursion in computer programming defines a function in terms of itself.
(...) The great advantage of recursion is that aninfinite set of
possible sentences, designs, or other data can bedefined, parsed, or
produced by a finite computer program.
Here are examples (adapted in Elica Logo) :
; factorial (recursive)
to r_factorial :n
if :n <= 1 [output 1]
output :n*r_factorial :n-1
end
print "'Recursive factorial'
print r_factorial 5
; factorial (iterative)
to i_factorial :n
make local "result 1
repeat :n [make "result :result*(repeat)]
output :result
end
print "'Factorial with iterative loop'
print i_factorial 5
Recursion versus iteration
In the "factorial" example the iterative implementation is likely tobe
slightly faster in practice than the recursive one. This result
istypical, because iterative functions do not pay the
"function-calloverhead" as many times as recursive functions, and that
overhead isrelatively high in many languages.
Another possible reason for choosing an iterative rather than arecursive
algorithm is that in today's programming languages, the stackspace
available to a thread is often much less than the space availablein the
heap, and recursive algorithms tend to require more stack spacethan
iterative algorithms. However, see the caveat below regarding thespecial
case of tail recursion.
Tail-recursive functions
Tail-recursive functions are functions ending in a recursive call.
The significance of tail recursion is that when making a
tail-recursivecall, the caller's return position need not be saved on
the call stack;when the recursive call returns, it will branch directly
on thepreviously saved return position. Therefore, on compilers which
supporttail-recursion optimization, tail recursion saves both space and
time.
The question is : does any Logo implement tail recursion ? and why not ?
__._,_.___
LogoForum messages are archived at:
http://groups.yahoo.com/group/LogoForum
|
