<div dir="auto">Warning ... recursion is like spicy Thai or Mexican food ... if you are not used to it, it can make your head explode!<div dir="auto"><br></div><div dir="auto">But when safely in the hands of responsible people it can give valuable information about conceptual complexity.</div><div dir="auto"><br></div><div dir="auto">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.</div><div dir="auto"><br></div><div dir="auto">So we have a dilemma: how do we shield the tender minded from recursive descriptions while sharing their beautiful simplicity with the initiated.</div><div dir="auto"><br></div><div dir="auto">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.</div><div dir="auto"><br></div><div dir="auto">In modern schools, prerequisites  must be met before admission to an advanced course.</div><div dir="auto"><br></div><div dir="auto">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."</div><div dir="auto"><br></div><div dir="auto">I'm going to try to make this simple enough that someone with no previous experience with recursion can see what is going on.</div><div dir="auto"><br></div><div dir="auto">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.</div><div dir="auto"><br></div><div dir="auto">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.</div><div dir="auto"><br></div><div dir="auto">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.</div><div dir="auto"><br></div><div dir="auto">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."</div><div dir="auto"><br></div><div dir="auto">If you do a directed graph of the function</div><div dir="auto"><br></div><div dir="auto">x---->f(x), where f(x) =(18-x)/2,</div><div dir="auto"><br></div><div dir="auto">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.</div><div dir="auto"><br></div><div dir="auto">So apparent circularity in definition may lead unambiguously (in some cases) to a well-defined number.</div><div dir="auto"><br></div><div dir="auto">In the algebra example, it is sufficient for the slope of the graph of f to be strictly less than one, in absolute value.</div><div dir="auto"><br></div><div dir="auto">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.</div><div dir="auto"><br></div><div dir="auto">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.</div><div dir="auto"><br></div><div dir="auto">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. </div><div dir="auto"><br></div><div dir="auto">This is not in any way an efficient procedure, but it is amenable to logically precise, concise, conceptually simple verbiage.</div><div dir="auto"><br></div><div dir="auto">Even the lexicographical order itself that is needed for placing the temporarily removed (last) word into its proper place is easily defined recursively:</div><div dir="auto"><br></div><div dir="auto">(For simplicity assume no other alpha numeric characters like hyphens, spaces, numerals, etc.)</div><div dir="auto"><br></div><div dir="auto">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.</div><div dir="auto"><br></div><div dir="auto">To Be Continued....</div><div dir="auto"><br></div><div dir="auto"><br></div><div dir="auto"><br></div><div dir="auto"><br></div><div dir="auto"><br></div><div dir="auto"><br></div><div dir="auto"><br></div></div>