Mailing List Archive: 49091 messages
  • Home
  • Script library
  • AltME Archive
  • Mailing list
  • Articles Index
  • Site search
 

Stack depth & Recursion

 [1/5] from: robbo1mark:aol at: 9-Jul-2001 12:10


Joel / everybody, Here's a little test func to find stack depth via recursion.
>> recfun: func [x][prin [x #" "] x: x + 1 recfun x]
try
>> 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. Maybe this is different on other platforms / versions, and I suppose the stock answer would be "it isn't wise to speculate on these things....platforms...versions... ..blah blah blah!" Which is fair enough as I'm not saying these things don't make for practical implementation variances. That's all I can think of. cheers, Mark Dickson

 [2/5] from: deadzaphod:flyingparty at: 10-Jul-2001 0:32


> Here's a little test func to find stack depth > via recursion.
<<quoted lines omitted: 5>>
> 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 ;-)

 [3/5] from: jeff:rebol at: 10-Jul-2001 8:53


Howdy, Cal:
> 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!
Neato! Inspired by your approach to the problem, below is my stab at it. -jeff ;------------------------------------------------------- do-tail-func: func [ "Does a tail-recursive function" word [word!] "The function name" args [block!] "Function arguments" locals [block!] "Function locals" body [block!] "Function body" args1 [block!] "Initial args to function" /local collect-args f ][ collect-args: func args compose/deep [throw reduce [(args)]] set word :collect-args f: function compose [[throw] (args)] locals body forever [args1: catch compose [f (args1)]] ] halt ;-examples: do-tail-func 'f1 [x][][ if x > 100000 [return "Done."] prin [x #] f1 2 * x ] [1] do-tail-func 'recfun [x] [] [ print x recfun x + 1 recfun x ] [1]

 [4/5] 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

 [5/5] from: joel:neely:fedex at: 10-Jul-2001 14:11


Hi, all, Slight correction, to prevent my face from being *too* red... Joel Neely wrote:
> ... and can do the canonical Fibonacci example (using a helper > function) as follows:
<<quoted lines omitted: 11>>
> ] > fib: func [i [integer!]] [-fib 0 1 i]
Of course, there's no point in making FIB a partial function when it's so easy to make it a total function instead!!! .fib: recurrence [a b n] [n <= 0] [a] [a + b a n - 1] fib: func [n [integer!]] [ either all [negative? n even? n] [ - .fib 0 1 abs n ][ .fib 0 1 abs n ] ] use [i] [ repeat j 21 [i: j - 11 print [i fib i]] ] -10 -55 -9 34 -8 -21 -7 13 -6 -8 -5 5 -4 -3 -3 2 -2 -1 -1 1 0 0 1 1 2 1 3 2 4 3 5 5 6 8 7 13 8 21 9 34 10 55 -jn- --------------------------------------------------------------- There are two types of science: physics and stamp collecting! -- Sir Arthur Eddington joel-dot-neely-at-fedex-dot-com

Notes
  • Quoted lines have been omitted from some messages.
    View the message alone to see the lines that have been omitted