[REBOL] Re: Stack depth & Recursion
From: deadzaphod:flyingparty at: 10-Jul-2001 0:32
> Here's a little test func to find stack depth
> via recursion.
> >> recfun: func [x][prin [x #" "] x: x + 1 recfun x]
> >> recfun 1
> 1 2 . . . 3146 3147 ERROR!
> ** Internal Error: Stack overflow
> ** Near: x #" "
> I've got REBOL/Core 2.5 and it always seem to halt
> at 3148 stack depth.
Funny, right now I'm at around 300000 and still running... ;-)
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!
Cal
-><-
REBOL [ Title: "Tail recursion eliminator" ]
tail-func: func [
"Defines a function that uses tail-recursion"
word [word!] "The function name" args [block!] locals [block!] body
[block!]
] [
set word function args append locals [
tailfunc args tailfunc-context return-value code-block
] append reduce [
; initialize locals here
to-set-word 'tailfunc-context context reduce [
to-set-word word 'function args [] [ throw/name bind args 'local
'tf ]
]
to-set-word 'args 'bind copy args to-lit-word 'local
to-set-word 'tailfunc 'function args locals 'bind copy body 'in
'tailfunc-context
to-lit-word 'self
][
; the code that really does the work
unset 'return-value
bind args 'local
until [
code-block: head insert tail copy [return-value: tailfunc ] reduce
args
set args catch/name code-block 'tf
value? 'return-value
]
return-value
]
function args locals body
]
; example:
; >> tail-func 'recfun [x] [] [prin [x #" "] x: x + 1 recfun x]
;>> recfun 1
; now watch it run ;-)
