To put it simply tail-end recursion is where the recursion is the last action that occurs, i.e. no further processing occurs after recursion to (i+1), I think statistics show that most uses of recursion are in fact tail-end. Functional programming tends to rely on heavy use of recursion, and thus on heavy use of tail-end recursion.
-----Original Message----- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Maxim Olivier-Adlhoch Sent: Thursday, October 09, 2003 2:23 PM To: [EMAIL PROTECTED] Subject: [REBOL] Re: Tail end recursion sorry if I'm not versed in lisp but what exactly is a tail end recursion? -MAx --- "You can either be part of the problem or part of the solution, but in the end, being part of the problem is much more fun." > -----Original Message----- > From: Ged Byrne [mailto:[EMAIL PROTECTED] > Sent: Thursday, October 09, 2003 5:17 AM > To: [EMAIL PROTECTED] > Subject: [REBOL] Re: Tail end recursion > > > > Thanks for that. I look forward to the day that I can > understand it :) > > --- Maarten Koopmans <[EMAIL PROTECTED]> wrote: > > > > Another quick question: does Rebol optimise tail > > end > > > recursion like Lisp and Scheme? > > > > > > > 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] > > > > -- > > To unsubscribe from this list, just send an email to > > [EMAIL PROTECTED] with unsubscribe as the > > subject. > > > > ______________________________________________________________ > __________ > Want to chat instantly with your online friends? Get the FREE Yahoo! > Messenger http://mail.messenger.yahoo.co.uk > -- > To unsubscribe from this list, just send an email to > [EMAIL PROTECTED] with unsubscribe as the subject. > > -- To unsubscribe from this list, just send an email to [EMAIL PROTECTED] with unsubscribe as the subject. -- To unsubscribe from this list, just send an email to [EMAIL PROTECTED] with unsubscribe as the subject.
