User:WillNess/sandbox

• User:WillNess/Sieve of Eratosthenes

• User:WillNess/Haskell primes one-liners

• Recursion - maze example: copies is the key, but they deleted it.

• User:WillNess/Fixed-point combinator

Sieve of Eratosthenes

This is the key difference of the sieve from using trial division to sequentially test each candidate number for divisibility by each prime.

to change into:

1. This is the key characteristic feature of the sieve that distinguishes it from just using trial division to sequentially test each candidate number for divisibility by each prime.
2. This is the sieve's key distinction from using trial division to sequentially test each candidate number for divisibility by each prime.
3. This is the key difference of the sieve as opposed to using trial division to sequentially test each candidate number for divisibility by each prime.
4. This is the key difference of the sieve as opposed to using trial division, sequentially testing each candidate number for divisibility by each prime.
5. This is the key difference of the sieve in comparison to using trial division to sequentially test each candidate number for divisibility by each prime.
6. This is the key difference between the sieve and trial division being used to sequentially test each candidate number for divisibility by each prime.

Informal definition

Recursion is the process a procedure goes through when one of the steps of the procedure involves invoking the procedure itself. A procedure that goes through recursion is said to be 'recursive'.

To understand recursion, one must recognize the distinction between a procedure and the running of a procedure. A procedure is a set of steps based on a set of rules, while the running of a procedure involves actually following the rules and performing the steps. As an analogy, a procedure is like a written recipe, whereas running a procedure is like actually preparing the meal.

Recursion is related to, but not the same as, a reference within the specification of a procedure to the execution of some other procedure. For instance, a recipe might refer to cooking vegetables, which is another procedure that in turn requires heating water and so forth. However, a recursive procedure is where (at least) one of its steps calls for a new instance of the very same procedure, like a sourdough recipe calling for some dough left over from the last time the same recipe was made.

When a procedure is defined as such, this immediately creates the possibility of an endless loop; recursion can only be properly used in a definition if the step in question is skipped in certain cases so that the procedure can complete, like a sourdough recipe that also tells one how to get some starter dough in case they have never made it before.

But even if it's properly defined, a recursive procedure is not easy for humans to perform, as it requires distinguishing the new from the old, partially executed invocation of the procedure; this requires some administration as to how far various simultaneous instances of the procedures have progressed. For this reason, recursive definitions are very rare in everyday situations.

An example of recursion in practice would be the following procedure of finding a way through a maze:

1. Proceed forward until reaching either an exit or a branching point (a dead end is considered a branching point with 0 branches).
2. If the point reached is an exit, terminate. Otherwise try each branch in turn, each time using the same procedure.
3. If there are no more branches to try, return to the previous branching point on the path that led to this branching point and report failure.

Whether this actually defines a terminating procedure depends on the nature of the maze: it must not allow loops. Executing this procedure as one monolithic process requires carefully recording all currently explored branching points, and which of their branches have already been exhaustively tried.

But executing it under the recursive paradigm is simple. Each time a process reaches a branching point, a new copy of the procedure is made. It doesn't care how it got there, it just starts new copies of itself for each branch and awaits each copy's report in its turn. If one of the copies had encountered the exit, we're out, and everything is stopped. But if this process got all the reports back it means we're still in the maze, so it just reports its failure back to that process which had spawned / activated / called it.

And that is all we need to know. Each copy takes care of its own proceedings, so the exhaustive testing and maintaining of records happens all by itself when copies do their job by creating more copies of the procedure doing their job according to the same specifications, each maintaining its own records.

Thanks to recursion we don't need to think about all that. Programming with recursion is thinking in the small, is about being here and now. It works when the local situation corresponds to the global one so that solving the global problem can be formulated in terms of solving the last single step after having solved all the self-similar sub-problems.