Tail end recursion

No, but I wrote a function that does this. Only for tail recursive functions though. And gives you good insight in cracking some REBOL nuts ;-) See below.... ---------------------------------------- REBOL [] tail-func: func [ {Returns a function that handles tail-recursion transparently.} args [block!] body [block!] /local _*meta-func _*meta-spec _*meta-body _*statement _*comm _*p1 _*p2 _*r _*w ] [ _*meta-spec: append/only copy [] args _*meta-body: append/only copy [] body ;matches refinements and copies refinements to our command _*p1: [ set _*r refinement! (either get bind to-word _*r '_*comm [append _*comm mold _*r _*ref-mode: on][ _*ref-mode: off ])] ;matches words and copies their values to the statement if ref-mode on _*p2: [ set _*w word! (if _*ref-mode [ append/only _*statement get bind to-word _*w '_*comm])] _*meta-func: copy [ ;The use context is accessible from the wrapper function that ;eliminates tail recursion. It plays the role of a stack frame ;it implements a goto like behaviour in case of tail recursion use [ _*loop-detected _*myself _*innerfunc _*loops _*myspec _*myspec2 _*mycall] [ ;some static initialization of the use context varaiables _*loops: 0 _*loop-detected: false _*mycall: copy [] _*innerfunc: func (_*meta-spec) (_*meta-body) _*myspec: copy first :_*innerfunc _*myspec2: either found? find _*myspec /local [append copy _*myspec [_*ref-mode _*p1 _*p2 _*r _*w _*comm _*statement _*ret]] [append copy _*myspec [/local _*ref-mode _*p1 _*p2 _*r _*w _*comm _*statement _*ret]] insert/only _*myspec2 [catch] ;The function that is returned from the use context _*myself: func _*myspec2 [ ;How deep in a loop am I? _*loops: _*loops + 1 ;These parse rules extract how I am called ;(which refinements and so) _*p1: [(_*p1)] _*p2: [(_*p2)] _*ref-mode: on ;Our initial call _*comm: copy {_*innerfunc} ;Our initial statement _*statement: copy [] ;Generate our statement and call parse _*myspec [ any [ _*p1 | _*p2 ]] insert _*statement to-path _*comm ;Copy it in the use context so it survives ;a loop (_*mycall is the 'goto args) _*mycall: copy _*statement if _*loops = 2 [ _*loops: 1 _*loop-detected: true return ] ;Until we are no longer in loop-detection mode until [ _*loop-detected: false set/any '_*ret do bind _*mycall '_*loops not _*loop-detected ] ;Use context cleanup _*loops: 0 _*loop-detected: false _*mycall: copy [] ;return our value return get/any '_*ret ];_*myself: func ... ];use context ];meta-func ;return our function.... do compose/deep _*meta-func ] ;example usage f: tail-func [x][x: x + 1 print x f x]

Well, it took some time to write it ;-) It is a very powerful demonstration of REBOLs ability to do most things you want if *you* are up to it. What does this script do? It creates a "hidden" context using the 'use construct. The value returned from the code block of 'use is a function that has access to all these words/values. So... the use context can act as an extra stack frame. This is exactly what it does: it sets a flag for a function (metafunc) to inidicate recursive calling. Innerfunc is inside metafunc and is your actual code. Metafunc simply counts and implements a goto with throwing away the current stack frame (local words). All the p1 and p2 stuff is to pass/count refinements. Enjoy your headache ;-) --Maarten

...

Recursion and looping are just two ways of expressing that something is to be repeated. In both cases one needs a terminating condition (unless the process is to run forever...) The example given earlier was a tad to trivial to make that point, but consider instead the slightly more complete example: forr-count: func [limit [integer!]] [ for i 0 limit 1 [print i] ] As we all know, this is just syntactic sugar for: while-count: func [limit [integer!] /local i] [ i: 0 while [i <= limit] [ print i i: i + 1 ] ] Notice that this version clearly states the initial "state" (I = 1), the condition for continuing the computation (I <= LIMIT), and the evaluation to occur for each continued case (PRINT and increment). Those same three ingredients are required to write an equivalent recursive function: rec-count: func [limit [integer!] /local .rec-count] [ do .rec-count: func [ i [integer!] .limit [integer!] ][ if i <= .limit [ print i .rec-count i + 1 .limit ] ] 0 limit ] Notice that every evaluation path through the inner function (.REC-COUNT) either terminates the computation or ends with a recursive call on itself, and every call to the inner function is the last thing in an execution path. (There's one of each.) In such cases, some languages/implementations can avoid the state-saving/restoration normally associated with beginning a subordinate evaluation -- in other words, they transform the recursive inner function above into a loop. REBOL does not. Sometimes the clearest/simplest specification for how to solve some problem is based on a divide-and-conquer strategy, where the sub-problems are either trivial to solve or are smaller cases similar to the original problem. In these cases, it is often easier to write a recursive solution. If the state management of the recursive implementation is too costly, one can (attempt to! ;-) formally transform the recursive solution into an iterative one; sometimes that's easy and sometimes not. (*) For more on this subject, please see http://www.rebolforces.com/articles/ria/ and for more on why recursion isn't complicated, see http://www.rebolforces.com/articles/metaphors/ HTH! -jn- (*) For an example of a problem that's easy to solve recursively, but which takes a bit of thought to solve iteratively (or in closed form! ;-), consider the old Fibonacci numbers. The original problem can be framed as follows: Begin a pair of new-born rabbits (one male, one female). When a pair of rabbits reaches age one month, they begin breeding, with a one-month gestation period, and breeding again immediatly after birth. Each breeding produces a pair of rabbits (one mail, one female). How many pairs of rabbits does one have each month (assuming that rabbits are immortal, food is infinitely available, etc...) Classify them as mature (at least one month old, breeding every month) and immature (just born, not mature for one more month). This give us the following population chart (in pairs): Month Mature Immature Total ----- ------ -------- ----- 1 0 1 1 2 1 0 1 3 1 1 2 4 2 1 3 5 3 2 5 etc... In other words, all pairs (immature or mature) which were alive last month are still alive, and all mature pairs from last month have produced new pairs. But the mature pairs last month are just the total population the month before! Finally, during the first two months we only have the original pair (immature or mature), so we get rfib1: func [n [integer!]] [ either n < 3 [1] [(rfib1 n - 1) + (rfib1 n - 2)] ] A little "programming algebra" produces the equivalent iterative form ifib1: func [n [integer!] /local a b] [ a: 0 b: 1 loop n [ a: (b: b + a) - a ] a ] But it takes a bit more mathematics to produce the equivalent closed form solution cfib1: func [n [integer!] /local r] [ r: square-root 5 ((1 + r / 2) ** n) - ((1 - r / 2) ** n) / r ] So recursion and iteration both have their places! ;-) -- ---------------------------------------------------------------------- Joel Neely joelDOTneelyATfedexDOTcom 901-263-4446 Counting lines of code is to software development as counting bricks is to urban development.

Nope.

F: tail-func [x][if x > 1000 [ return x ] x: x + 1 print x f x] Which shows the difference with your example. I use tail-func to recursively traverse a tree structure that is mapped to a table in a relational database, updating the number of leafs per node. So I traverse the tree passing in the tree, updating the counters, and then calling itself with the rest of the tree (subtree). --Maarten

You stop by having a condition, and only calling again if that condition is true. So while [keepGoing] [do something] is equivalent to something: func [keepgoing][if [keepgoing][do something[keepgoing]]]

Translation: I'm sorry, but I don't understand english. Kind regards, H. Kalka And for Mr. Kalka ... Hallo Herr Kalka, Irgendwie haben Sie eine Email erhalten, die an eine englischsprachige Email-Liste gerichtet war. Falls es sich um einen einzelnen Irrläufer gehandelt hat, sollte sich das für Sie erledigt haben, falls nicht, dann sendes Sie bitte eine Email an [rebol-request--rebol--com] mit dem Subject: unsubscribe danach sollten Sie aus der Liste wieder ausgetragen sein. Mit freundlichen Grüßen, Ingo Hohmann

Here's the long answer from Holger Kruse - see the bottom http://www.compkarori.com/vanilla/display/continuations -- Graham Chiu http://www.compkarori.com/vanilla