Mailing List Archive: 49091 messages
  • Home
  • Script library
  • AltME Archive
  • Mailing list
  • Articles Index
  • Site search

[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