[REBOL] Re: Stack depth & Recursion
From: joel:neely:fedex at: 10-Jul-2001 16:58
Hi, Cal!
Cool!
Cal Dixon wrote:
> After seeing this discussion I wrote a little hack to implement
> tail recursion elimination. I'm sure it could be done better
> (Joel? Ladislav? anybody wanna fix this thing up?) but works
> well enough that I'll probably use it the next time I need deep
> recursion. (wow.. up to 452000 already) anyway, here it is, enjoy!
>
...
> ; example:
> ; >> tail-func 'recfun [x] [] [prin [x #" "] x: x + 1 recfun x]
> ;>> recfun 1
> ; now watch it run ;-)
>
I'm not quite as ambitious! Rather than trying to make something
that looks like the current FUNC or FUNCTION, I thought about the
idea that a typical tail-recursive function looks something like
the following schema
blort: func [arg-a arg-b ... arg-z] [
either termination-condition [
final-expression
][
blort expr-a expr-b ... expr-z
]
]
For example, the tail-recursive block-summer from earlier:
>> nums: [90 1 45 52 42 19]
== [90 1 45 52 42 19]
tr-sum: func [b [block!] /local -tr-sum] [
-tr-sum: func [b [block!] s [number!]] [
either tail? b [s] [-tr-sum next b s + first b]
]
-tr-sum b 0
]
>> tr-sum nums
== 249
fits that scheme with
[b [block!] s [number!]]
as the arguments,
tail? b
as the exit condition,
s
as the exit expression, and
next b s + first b
as the arguments to the recursive call.
Thinking of it that way led me to define this:
recurrence: function [
"Create a tail-recurrence function"
funargs [block!]
exitcond [block!]
exitexpr [block!]
recurrence [block!]
][
pureargs funbody
][
pureargs: copy/part funargs any [find funargs /local length?
funargs]
while [not tail? pureargs] [
either word? first pureargs [
pureargs: next pureargs
][
remove pureargs
]
]
pureargs: head pureargs
funbody: compose/deep [
while [not (exitcond)] [ set [(pureargs)] reduce
[(recurrence)] ]
(exitexpr)
]
func funargs funbody
]
which can define our block-summer by saying:
rr: recurrence [b [block!] s [number!]] [
tail? b
][
s
][
next b s + first b
]
>> rr nums 0
== 249
and can do the canonical Fibonacci example (using a helper function)
as follows:
-fib: recurrence [
"tail-recurrence function for Fibonacci numbers"
a [integer!] "current value"
b [integer!] "prior value"
n [integer!] "Fibonacci index desired"
][
n <= 0
][
a
][
a + b a n - 1
]
fib: func [i [integer!]] [-fib 0 1 i]
use [i] [
repeat j 10 [i: j - 1 print [i fib i]]
]
which gives us the standard
0 0
1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34
Have fun!
-jn-
--
My hero, zero. Such a funny little hero,
But till you came along, we counted on our fingers and toes.
-- Schoolhouse Rock (1973)
joelDOTneelyATfedexDOTcom
