## [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