[REBOL] Re: On ordinal and cardinal numbers...
From: joel:neely:fedex at: 10-Jul-2001 2:39
Hi, Paul,
Paul Tretter wrote:
> Since I'm relatively new at programming, can you explain what
> is meant by recursion and iteration? I just want to learn ;)
>
Certainly!
Iteration
is just the conventional jargon for "repetition" (as
in "let me re-iterate" instead of "let me repeat"). The words
LOOP, FOR, FOREACH, UNTIL, and (of course) REPEAT are all ways
of doing iteration in REBOL.
Recursion
basically means something which is defined in terms
of itself, such as a function that calls itself, directly or
indirectly. (The standard joke, from the Jargon File, is
recursion n. See recursion. See also tail recursion.
but we'll cover "tail recursion" a bit later.) Sometimes you
also hear reference to "resursive structures", which means
structures whose content may be of the same type as the whole
structure (e.g. blocks within blocks). Such structures are
often processed with -- what else? -- recursive functions.
To illustrate, suppose we have a block of numbers:
>> nums: [90 1 45 52 42 19]
== [90 1 45 52 42 19]
We can define the sum iteratively as
repeat the process
add a number to the total
until all numbers have been added
One iterative solution to adding up the numbers in the block is:
tot: 0 foreach num nums [tot: tot + num] tot
== 249
If we didn't have the nice handy FOREACH function we could write
tot: 0 numref: nums while [not tail? numref] [
tot: tot + first numref numref: next numref
] tot
== 249
(among *many* other iterative possibilities).
In contrast, if we want to write a recursive solution, we start
by defining the sum of a collection of numbers this way:
the sum of an empty collection is zero
the sum of a non-empty collection is
the first number plus the sum of the rest of the numbers
which leads us to this recursive solution in REBOL
sum-o-nums: func [b [block!]] [
either tail? b [0] [(first b) + sum-o-nums next b]
]
>> sum-o-nums nums
== 249
If we visualize the work of this function, we can get a couple of
useful insights. Using a tiny block of numbers, we can work
step-by-step through the computation by rewriting:
sum-o-nums [2 3 4]
(first [2 3 4]) + sum-o-nums next [2 3 4]
2 + sum-o-nums [3 4]
= (and now we'll pick up the pace)
2 + (3 + sum-o-nums [4])
2 + (3 + (4 + sum-o-nums []))
2 + (3 + (4 + 0))
2 + (3 + 4)
2 + 7
9
Forgive me if I belabor the obvious, but the key here is that
all of the earlier additions are "on hold" until we get all the
way to the 0 at the "bottom"; we can then begin the process of
resuming the pending additions and working back up to the top
answer.
The effort of keeping track of partially-completed work (a
sort-of "virtual to-do list", managed by the interpreter)
is why iteration is usually faster than recursion for simple
cases like the example above.
On the other hand, some not-so-simple tasks that don't have an
obvious iterative solution are fairly easy to express using
recursion, such as the case of "pretty-printing" a block
structure as an indented "outline":
pp: func [b [block!] /local -pp] [
-pp: func [x ind [string!]] [
either block? x [
print [ind "["]
foreach y x [-pp y join ind " "]
print [ind "]"]
][
print [ind x]
]
]
-pp b ""
]
>> pp [2 [3 5 7 [9]] 11 13]
[
2
[
3
5
7
[
9
]
]
11
13
]
Here the internal functinon -PP invokes itself (with a
deeper indentation prefix) to deal with nested blocks,
so it is recursive. Keeping track of where we are in the
block structure is sufficiently tedious that writing this
function recursively is simpler than writing it as an
iterative function.
Finally, I promised to get back to "tail recursion", which
I'm doing at the tail of the email. ;-) Consider this
recursive-looking function to sum up our block of numbers.
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
That inner function -TR-SUM certainly *looks* recursive,
because it calls itself. However, that call is done in
such a way that there isn't really any "pending" work to
do after the recursive call (except for simply returning
the result). A really clever compiler (or interpreter) will
be able to treat that function as if it had been written
this way:
ti-sum: func [b [block!] /local -ti-sum]
[
-ti-sum: func [b [block!] s [number!]]
[
while [not tail? b] [
set [b s] reduce [next b s + first b]
]
s
]
-ti-sum b 0
]
>> ti-sum nums
== 249
turning the recursion into an iteration where the arguments
are repeatedly adjusted until arriving at the final answer.
HTH!
-jn-
---------------------------------------------------------------
There are two types of science: physics and stamp collecting!
-- Sir Arthur Eddington
joel-dot-neely-at-fedex-dot-com
