Talk:Recursion

What's the deal with this article totally missing a recursive definition of recursion. Its a fairly common joke, it's very funny the first time you read it (and for many people, wikipedia is the first time) and is generally harmless. Now I look back through the article's history and found that Leibniz has been reverting such clever links on multiple occasions.

Looking at this discussion it seems like most people here are in favour of a cute recursive definition as long as it doesn't obstruct the article, which I believe my link didn't and I am positive the previous link that was put in the "see also" section by someone else didn't obstruct anything.

I notice also that Mr Leibniz has never once made a single comment on this talk page, and has reverted the page without any kind of explanation, something that is forbidden by wikipedia policy. By the looks of this discussion, it seems that this guy is the only person around here that doesn't find that joke funny at all. I sure as hell did when I first read it.

So come on leibniz, have a sense of humour about this, its not as if a little recursion in an article about recursion really hurts anything.

--Scarlet 23:48, 8 Nov 2004 (UTC)

For what it's worth, I don't think the jokes are appropriate. For people reading the article who honestly are not familiar with what recursion is, the jokes can only confuse. They only make sense once you understand, but that's the purpose of the article. A "joke" that many people won't get will probably only annoy people (trying to learn). Revolver 11:54, 9 Nov 2004 (UTC)

Because it's wrong, that's why. It is not merely a cute harmless joke, it actively obscures the distinction between recursion and circularity: recursion terminates; circularity does not. There, is that enough explanation for you? -- Antaeus Feldspar 01:40, 26 Nov 2004 (UTC)

Recursion doesn't have to terminate. Circularity is merely a special form of recursion that obviously doesn't terminate. -- Bernhard Bauer 18:14, 7 Feb 2005 (UTC)

In example 2.1, there's the following claim :

0 is in N

if n is in N, then n+1 is in N

The natural numbers is the smallest set satisfying the previous two properties.

I think smallest is debatable as the set of Natural numbers is countably infinite and I feel there exists only a partial order among countably infinite sets in terms of cardinality. Also, any set that exactly meets the above two properties is identical with the set of Natural Numbers itself, right? -- Sundar

I agree that calling it the smallest set is debatable. But can you explain why you say there is a partial order with respect to the cardinality of countably infinite sets? In fact they are all equal in cardinality and represented by the same infinite number <math>X0<math> (aleph nought)

--Sanjeeth

Sanjeeth, I read about aleph nought only much later than I posted this. Before that, I thought, there may be countably infinite sets of unequal cardinality. Now, I understand that all countably infinite sets have a notional cardinality of <math>X0<math>. Thanks for pointing out.

-- Sundar 05:39, May 6, 2004 (UTC)

There is a partial order on all countably infinite sets — namely set inclusion. That's not the issue here. The "smallest" part means that every other set that satisfies 1 and 2 contains N. This set exists by showing such a set exists (usually using the axiom of infinity) and then taking the intersection of all such sets. This intersection is contained in all sets satisfying 1 and 2. Revolver 21:44, 9 Oct 2004 (UTC)

Thanks Revolver. Got your point. -- Sundar 05:26, Oct 11, 2004 (UTC)

Hilarious!... though I think someone should write a real article here as well... -- Simon J Kissane

We could have both the joke and an encyclopedia article, thanks to the ability to pipe links. For instance, the "recursion" link on the "recursion" page could be piped to "recursion definition" or somesuch.

Hmm, I liked the old way as it is not actually recursive any more (it only looks like it is). I think we should change it back, but add a link to the definition below the See recursion line. --BlckKnght

This is good. The joke's still there, but if people don't get it they can get the actual definition. Thanks. --Robert Merkel

Recursion is not only "the definition of a function in terms of itself". It is any procedure defined in terms of itself. There are recursively defined sets, for examples. All these concepts are related, of course.

I think the two paragraphs about generative grammar in the introduction are very nice, but they belong in the body of the article. -- Miguel

The Recursive Definiton of Recursion *is* imho, a valid definition of the term. It's very short, and some people seem to think it's funny. Fine by me, but I don't think peoples' strange senses of humor have anything to do with writing a complete article. Keep it in there.

I think your opinion is wrong. How does simply providing a link to the page you are already on define recursion? It is an example of recursion, not a definition. Pete/Pcb21 (talk) 16:32, 31 Jan 2004 (UTC)

There are 3 answers to this (shortest to longest)

mean but valid:

see:recursion

NPOV:

Several Geek Jargon Dictionaries give this as the definition. It is beyond dispute that some geek jargon dictionaries do give this as (a) definition of recursion.

Logic:

Lets call a recursive definition of X "a definition that defines X in terms of X itself".
The _shortest_ recursive definition of X would then be : " see : X "
This is a rather trivial definition. It doesn't usually bring much to the table in actually explaining anything about X. But there's at least one exception:

The shortest recursive definition of recursion is: " see: recursion ".
This definition has the interesting property of actually *being* a recursion.

Now let's look at an example for a moment: The most complete definition of The Collected Works Of Shakespeare would actually consist the entire written collected works of Shakespeare. Such a definition might be just a tad unwieldy, but it *is* a definition. Whatever you say about it, the complete definition of something is certainly going to be a *valid* definition.

The Recursive Definition Of Recursion *IS* itself a recursion, so it completely contains that which it describes. So just like in the shakespeare example, it could be said that the recursive definition is in fact a complete definition.

Oh, and in umb scheme , do NOT do:

 ( define recursion (lambda () (recursion)) )

. *ahem*

80.126.238.189 14:03, 2 Feb 2004 (UTC)

Contents

1 response

1 Existence proof of recursion
2 Can we get serious?
3 setting the record straight
4 Removed
5 reasons for removal
6 Response to Antaeus Feldspar's valid criticisms
7 Revising the intro
8 Corecursion

response

By that logic, a complete rebuttal of your third point is contained in the first sentence on this talk under this heading. Pete/Pcb21 (talk) 15:38, 2 Feb 2004 (UTC)

Quite so. Unfortunately the rebuttal is a trivial recursion, and doesn't seem to address the point at hand. ;)

I wrote a little bit of scheme (see above) which helps a lot. It basically reads "recursion = see: recursion". Sound familiar?

In scheme:

 ( define recursion (lambda () (recursion)) )

it expands to something like (not pure scheme here) :

 recursion = 
        ( lambda () 
            ( lambda ()  
                ( lambda () 
                    ( lambda ()
                        ( ...

Now why shouldn't you type that line in scheme? ;-)

By translating from english to scheme (and losing a bit of the fuzzyness of natural languages) maybe you'll see the meaning of the statement more clearly. It contains within itself a recursion! And catching a recursion red-handed is better than some second hand account of what a recursion is supposed to be.

But all the while I'm still just trying to explain someone elses opinion. Let's just say some people prefer recursion to be defined this way, those people are certain geeks in certain dictionaries (for instance the jargon file (http://www.jargon.org) ) , and leave it at that? 80.126.238.189 18:36, 2 Feb 2004 (UTC)

It is all right to argue about recursion in maths, but you should widen the scope to include natural languages and non-formal language processing, such as in transation from L1 to L2 to become more enlightening and reveal the morale for other knowledge areas. Apogr 19:15, 12 Feb 2004 (UTC)

Existence proof of recursion

I removed the existence "proof" of the recursion theorem. This is an old mistake that is (unfortunately) reproduced in some textbooks and by some teachers who should know better. A correct proof for the case of the natural numbers is given in Hungerford, "Algebra", before the group theory chapter. The point is that you are mixing language with meta-language, you are talking about a function BEFORE you have even shown that it exists. This is a no-on. You have to construct the function from the ground up as a subset of X × X. Revolver 01:31, 13 Mar 2004 (UTC)

Can we get serious?

Much as I like humor, and especially computer-related humor, I must protest that the recursion article is almost useless for readers who want to know something about recursion. As a computer expert myself, I can laugh at circular definitions of recursion like "See recursion" and even appreciate the insight of "you have to know what recursion is, to understand recursion".

But I think we need a general article, one which can be understood by laymen as well as by us *ahem* geniuses. --Uncle Ed 18:57, 7 Oct 2004 (UTC)

Hmm, well let's see. If you do manage to get the "see recursion" in one shot, you're home free, I guess. But what if you don't?

Hmm, it's a tricky one to explain starting from plain english (I learnt it starting from knowing structured programming). I'll ponder on it!

Do you know of any good approaches yourself? Kim Bruning 20:25, 7 Oct 2004 (UTC)

I like the visual approach. For the Dutch wikipedia i just rewrote parts of the article, using an image taken by pointing a webcam on the computerscreen. The principle of self-reference is used quite often in daily life, and even children should be able to understand it. Of course it's easy to make fun with recursion, but I think that the fun makes very clear what recursion is: "This phrase is not recursive" is probably a bit too abstract, but everyone should be able to understand the basics of recursion from "This phrase is not true". Another example is the use in hierarchical structures. You need to do something recursive if you want to list all your bosses at work (your boss, the boss of your boss, the boss of the boss of your boss, etc). --Taka 14:56, 9 Oct 2004 (UTC)

I'm not sure "This phrase is not true" is really an example of recursion. That seems to be Russell's paradox, which is something different. I'm not even sure "This phrase is not recursive" is really an example of recursion. In fact, I'm not even sure what it means, maybe "This phrase is not defined recursively"? It appears simply to be a true statement to me, if there is any "funny stuff" going on, it would seem to be with Russell's paradox again. Revolver 21:39, 9 Oct 2004 (UTC)

setting the record straight

Despite whatever a "geek dictionary" may say, "See: recursion" is NOT a definition of recursion, anymore than "See: giraffe" is a definition of a giraffe or "See: topological space" is a definition of a topological space. "See: recursion" is at best a tautology, i.e. "the definition of A is A", which is just trivial, not defining anything. Revolver 12:01, 9 Nov 2004 (UTC)

There is an extensive discussion of this a little higher up on the page. "See:recursion" is the exception that proves the rule. ;-) Kim Bruning 12:27, 9 Nov 2004 (UTC)

Well, you're just wrong. While it may be possible in math and computer science to define objects recursively in a precise and meaningful way, "See: recursion" does not tell you what recursion (the process or method of defining) is. To make it more clear: in non-well-founded set theory, if a person understands the theory, then it is possible to tell them what an object is by defining it recursively or circularly. However, this is not the same thing as telling them what the theory of non-well-founded sets is in the first place. Recursive or circular definitions are possible, but this is a way of defining objects, not the concept of recursion itself or some well-defined theory for defining objects recursively or circularly. If that were the case (sadly, is not) then learning what recursion is would be trivial and there would be no need for this article. Revolver 14:43, 9 Nov 2004 (UTC)

Restated: The recursive term is not guarded and doesn't have a minimal fixed point.CSTAR 03:04, 29 Dec 2004 (UTC)

Removed

Formally, the meaning of recursion requires the use of (least or greatest) fixpoints, as in domain theory. (For instance: the set of your ancestors is the least set containing your parents, and closed under the ancestor relation). It is however not strictly necessary to appreciate these foundational issues to grasp recursion.

Phrases like this have no place in the intro part. They only frighten a person from reading further. Mikkalai 03:23, 26 Nov 2004 (UTC)

reasons for removal

Paul13 has asked why the five paragraphs he added to the beginning of the article [1] (http://en.wikipedia.org/w/index.php?title=Recursion&diff=prev&oldid=10828432) were removed. Since I did the removing, I'll explain why:

Wikipedia articles try to conform to a certain style of writing; we in fact have a whole directory of the articles we have for ourselves, to try and edit up to this quality. One of the important aspects of good Wikipedia style is a good "intro" -- the very first paragraph of the article, which contains the article subject term in bold and gives the most concise, clear introduction to the subject. Like the lead paragraph of a newspaper article, a good guideline is "If the reader read just this first paragraph and no further, what would they have learned?"

No indication was made that the article as it stands had an inadequate intro, or one that needed to be replaced. That is, however, what the changes that were made did: they became the new intro of the article. Here is the intro as it existed:

In mathematics and computer science, recursion is a particular way of specifying (or constructing) a class of objects (or an object from a certain class) with the help of a reference to other objects of the class: a recursive definition defines objects in terms of the already defined objects of the class.

and here is what became the new lead paragraph intro:

Think recur or reoccur.

Here is the second, which applies only to recursive procedures, and ignores recursive definitions, which are also part of the general concept of recursion:

Recursion is the calling of a procedure from within that procedure. Therefore a procedure is recursive if one of the steps of the procedure involves running a new cycle of the procedure.

Even if there are problems with the existing intro (and no one mentioned such problems on the talk page before the changes were made) this "solution" does not actually solve the problems very well. In bluntness, it does not deserve to be the new intro of the article.

The alternative to removing it altogether would have been to refactor the material into the existing article. However, and again in bluntness, I could not find material worth refactoring. The article already contains examples and analogies, and the existing examples are much clearer. The remaining material contains additional inaccuracies, for instance the final paragraph:

It is important to note that a recursive procedure must complete every one of its steps; even if a new running is called, each running must wait for all of the internal runnings to complete, and then run through its final steps. What this means is that even if the entrée is an entire four course meal unto itself, once that meal is done, you still have to eat your dessert.

This is, at best, highly misleading. Take for instance the language Cilk, a C derivative for use on multiple-processor systems. In this language, the keyword spawn is used to mark procedures that can be executed in parallel to the parents that called them, and the keyword sync is used to mark a point where a parent procedure must make sure all its children have completed. A quicksort might therefore be programmed as follows (in cilk-like pseudocode):

cilk none qsort(array a, int left, int right) {
    while (left < right) {
        partition a into (elements < pivot, pivot, elements > pivot)
        spawn qsort(a, left, indexOfPivot - 1)
        left = indexOfPivot + 1
    }
    sync
}

This procedure divides the problem into two smaller procedures which could both be called recursively; however, it calls one recursively and handles the other itself (an example of tail recursion being transformed into iteration.) To say "each running must wait for all of the internal runnings to complete" creates the false impression that the procedure, having spawned off one of the smaller procedures recursively, cannot proceed with handling the smaller procedure it has reserved for itself, but instead must wait until the procedure it spawned recursively returns. This is not true; the point at which it must wait (the sync at the very end of the procedure) is after it has finished all its own work, not before it proceeds with its own work. It's true that on single-processor systems, the difference is moot -- but just as we are not talking solely about recursive procedures, we are not talking solely about recursion on single-processor systems.

This is why your material was removed. -- Antaeus Feldspar 17:54, 5 Mar 2005 (UTC)

Response to Antaeus Feldspar's valid criticisms

You seem to have more tech experience than I do, while my experience lies in explaining technical and complicated concepts to people who are neither technical nor particularly gifted in logical thought. What do you say that we work together to build a definition that will help the less technical browsers understand what recursion is?

First off, you have to realize that the kind of people who struggle to understand what recursion is are not the kind of people who are going to post criticism on the discussion board of an encyclopedia. Tech inhibited are likely not going to figure out how to post protests, even if they determine that they can. This is just beyond the scope of most people's awareness when it comes to computers and the internet. In addition, normal people are not the kind who brave the intellectual jungles of online encyclopedia definition discussion board. It is too scary to tangle with the savage geeks that roam these parts. Therefore, to conclude that the definitions are not too technical for the masses because none of those who post here are able to see that they are too technical seems to me to be an assumption made based on too select a sample of opinions.

I can tell you both from my professional experience, and due to complaints from well educated professionals and students who have tried and failed to understand recursion based on the definitions, that Wikipedia's definition of recursion is going over the heads of many who read it.

I think it would be preferable for my definition, after making changes based on you valid criticisms, to go under the heading, "definition for the none technical", "definitions for the rest of us", or some such thing. That would have been my preference to begin with, but I must admit I was not sure exactly how to make that happen. Perhaps you could be of service in this as well.

The definition that I wrote was originally specifically for recursion as it pertains to linguistics, as that is what I was asked to do. My experience with computer science recursion is apparently more limited than I was aware.

As per your critiques, would this be a more viable intro?

"Recursion is the calling of a procedure from within that procedure, or the product of a recursive procedure."

This portion:

was a slip that I did not intent. The point of this was to clear up that recursive procedures don't simply tangent off and never return. Many people seem to confuse a recursive function with a function that exits to another function. I likely should have written:

It is important to note that a recursive procedure must complete every one of its steps; even if a new running is called, each running must run through its final steps either while the other internal procedures run, or after they complete. What this means is that even if the entrée is an entire four course meal unto itself, you still have to eat your dessert.

How are these corrections? When you answer, try to put yourself in the mind set of someone who has no idea about mathematics, computer science or recursion. The most common problem people have when writing definitions is that they write something that gives the details of that things as opposed to explaining the relevance of those details.

Paul Osborne

Revising the intro

I think one of the problems we're facing with this articles is that recursion comes in two basic flavors: recursive definitions, and recursive procedures. Each is easy to describe on its own, but finding a concise yet precise definition that covers both is difficult. I think the article will become much more readable if we can find such a definition, make it the first sentence in the intro, and then go from that (necessarily) abstract definition to more concrete separate definitions of recursive definitions and recursive procedures. -- Antaeus Feldspar 18:07, 18 Mar 2005 (UTC)

Corecursion

Corecursion currently redirects to Recursion, but there is no mention of corecursion here. Can I request that someone either add one (it's not my area), or remove the redirect? --Malcohol 14:11, 2 Jun 2005 (UTC)

In fact, now that I've read the Recursion article, this may be an important distinction that is being overlooked. The humorous "definition of recursion" is described as "an erroneous recursive definition of an object, the error being the absence of the termination condition...". Yet the "recursive acronym GNU" has no such termination condition. I think some of the examples described as recursive may acually be corecursive. As I said, this isn't my area, but I think an example of a corecursive definition is the following: "The first element of the sequence s is 1 and the rest of it is equal to s". This is a valid definition of an object (the infinite list of ones) yet there is no base case. Of course, you may not believe in the existance of infinite objects, but let's leave that until later in the pub;).--Malcohol 14:41, 2 Jun 2005 (UTC)

Retrieved from "https://academickids.com:443/encyclopedia/index.php/Talk:Recursion"