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