[EM] Recursion for the Daring!

[Forest Simmons]

Warning ... recursion is like spicy Thai or Mexican food ... if you are not
used to it, it can make your head explode!

But when safely in the hands of responsible people it can give valuable
information about conceptual complexity.

Recursively defined procedures, while maximally succinct and conceptually
simple (in the minds of people used to them)  are often computationally
"hard", involving an impractically large number of simple, but highly
repetitive operatioms.

So we have a dilemma: how do we shield the tender minded from recursive
descriptions while sharing their beautiful simplicity with the initiated.

In ancient times secretive, exclusive societies like the Pythagoreans or
the Masons organized according to various levels of what might be called
"security clearance" in modern parlance.

In modern schools, prerequisites  must be met before admission to an
advanced course.

On the EM list, inquisitive but sensible people just give up if the going
gets too tough too soon; "Obviously this post was not intended for the
general public."

I'm going to try to make this simple enough that someone with no previous
experience with recursion can see what is going on.

The tricky (and clever) part of recursion is judicious use of what seems to
be circular definition, but is in reality a kind of convergent inwardly
spiraling reasoning.

If your first grade teacher asked you to define the number six, you might
say that it was the number just before seven, which would be true, but not
as helpful as saying the number just after five.

In the seventh grade a smart alec student might say that six is the number
that you get if you subtract it from 18 and divide the result by two.

This answer would highly displease your third grade teacher as an example
of circular definition. But the 7th grade algebra teacher would say, "This
kid has talent."

If you do a directed graph of the function

x---->f(x), where f(x) =(18-x)/2,

the picture you get is a spiral flow converging to the number 6 on the
number line.  If you graph y=f(x) on an (x, y) coordinate system and
connect points (x, y) to (y, f(y)) with arrows, you with get a "web"
diagram of the same underlying spiral structure converging to the point
(6,6) on the graph of y=x.

So apparent circularity in definition may lead unambiguously (in some
cases) to a well-defined number.

In the algebra example, it is sufficient for the slope of the graph of f to
be strictly less than one, in absolute value.

For recursively defined procedures it is sufficient that any self
referential part of the procedure be restricted to a set of lesser
cardinality than the "main" set being dealt with.

If you want to recursively define a procedure on a set of size n,
temporarily remove a member of the set. Then "recursively"apply the
procedure to the smaller set of size (n-1), and then re-incorporate the
member that was removed.

For example, to alphabetize a random list of words, remove any word from
the list, recursively alphabetize the rest of the list, and then finally
place the word that was removed into its proper place.

This is not in any way an efficient procedure, but it is amenable to
logically precise, concise, conceptually simple verbiage.

Even the lexicographical order itself that is needed for placing the
temporarily removed (last) word into its proper place is easily defined
recursively:

(For simplicity assume no other alpha numeric characters like hyphens,
spaces, numerals, etc.)

Find the first place (from the left end) of the two words where they do not
have the same letter. If that place is at the first letter of the word,
then precedence goes to the word whose initial letter is closer to the
front of the alphabet. Otherwise, temporarily remove the common initial
string of letters and apply the procedure recursively to the remaining
sub-strings of letters.

To Be Continued....
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20220110/c41b0fe8/attachment.html>