## [REBOL] Re: Tail end recursion

### From: joel:neely:fedex at: 9-Oct-2003 10:22

Hi, Maxim, and all Maxim Olivier-Adlhoch wrote:> so basically its like using recursion to do a loop? >...> but how does tail-end recursion stop? >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.