Talk:Recursion

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated B-class, Mid-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
B Class
Mid Importance
 Field: Foundations, logic, and set theory
One of the 500 most frequently viewed mathematics articles.

Archived discussion: Beginning to December 2008

Different image[edit]

I don't like the change to using Image:Itrecurs.jpg in the lede. The Droste poster is visually appealing and was actually used to sell cocoa, not custom-made just for this article. The newer image looks like one of those fake "motivational" posters. I don't see it as a net improvement over the Droste image. — Carl (CBM · talk) 22:13, 9 October 2008 (UTC)

Ok, some very clever jokester has made the page regarding recursion recursive, precluding any sort of meaningful knowledge on the subject at hand. Can we revert this, please?

67.171.141.220 (talk) 03:06, 11 April 2009 (UTC)

Restore please?[edit]

Ok, the new page on recursion is very clever, but does little to illuminate the intricacies of recursion as a mathematical, physical, and literary concept. Can we please revert the page so we can glean some useful information? Maybe a level of security too...

03:14, 11 April 2009 (UTC) —Preceding unsigned comment added by Tethros (talkcontribs)


Recursive Definition Compromise[edit]

To satisfy many people's want of a recursive definition (e.g. Recursion - see Recursion) without obstructing anything why don't we just add the following to the line at the top (with links to Recursion (Computer Science) etc.): For a practical definition of recursion see Recursion [with a link of course]. —Preceding unsigned comment added by 68.98.155.17 (talk) 04:20, 14 April 2009 (UTC)

No, that would be silly. — Carl (CBM · talk) 11:36, 14 April 2009 (UTC)
Agree with Carl. Paul August 02:11, 28 April 2009 (UTC)
I agree with Carl and Paul August. Ozob (talk) 22:45, 28 April 2009 (UTC)
I agree with Carl, Paul August and Ozob. Bemarenina (talk) 11:35, 15 September 2010 (UTC)
I agree with Carl, Paul August, Ozob and Bemarenina. --Joshua Issac (talk) 18:27, 11 November 2010 (UTC)
I agree with Carl, Paul August, Ozob, Bemarenina and Joshua Issac. SkpVwls (talk) 21:54, 11 November 2010 (UTC)
You are discussing the wrong article if you want to be so non-recursive, SkpVwls and all those with whom she/he agreed. 216.239.45.4 (talk) 22:57, 24 November 2010 (UTC)
I agree with myself (unanimously). Marc van Leeuwen (talk) 12:14, 16 May 2011 (UTC)

Recursion link in "See Also"[edit]

I'd be interested in opening an RFC on the topic of putting a link to Recursion in the "See Also" section. While it is a small point, I think it reflects the much wider issue of "Can Wikipedia afford to occasionally be less than deadly serious?". I firmly believe it can, and I feel that a humorous touch like this actually creates a better encyclopedia.

Thoughts anyone? Manning (talk) 18:05, 25 June 2009 (UTC)

I agree; the link-recursion-back-to-recursion meme is so widespread on the net that it makes Wikipedia look unnecessarily po-faced if it isn't permitted here. Provided that the textual content of the article itself is genuine and relevant, there's no harm at all in referencing the joke by means of a link or "see also" item. MarkSG (talk) 21:33, 23 July 2009 (UTC)
That see also thing has been discussed to death, and it never gains consensus. The reason for that is that this is an encyclopedia, not a jokebook. It makes us look unprofessional to include jokes in our articles. Many other things are widespread on the web, such as the word 'epic' and kewl spelling; we eschew those as well. We do describe the web meme here, which is the way we should handle it. See the section above for a previous discussion about this. — Carl (CBM · talk) 21:38, 23 July 2009 (UTC)
As far as I can see, the reason it never gains consensus is because a relatively small number of contributors are very opposed to it and repeatedly make their objections known. That's why I agree with Manning that an RFC process could be useful, as it might help to get a broader spectrum of views involved. If that then does result in a consensus (or even an observable majority) against including the link, then that's fine. But, equally, if an RFC supports inclusion, then it should be included. MarkSG (talk) 07:03, 24 July 2009 (UTC)
My first reaction to finding out such a harmless spot of humor is completely taboo was actually to take Wikipedia less seriously than before (I'm a very frequent user, and a strong proponent). Wikipedia has a couple rules I disagree with (none very strenuously), but this deserves at least a vote on the topic. It doesn't have to be a disambiguation link at the top of the article, but a link to it in the "see also" is harmless. A link in the first paragraph phrased as an example might even be completely appropriate, if done properly. Prgrmr@wrk (talk) 08:22, 24 July 2009 (UTC)
Can you explain how this makes you take wikipedia less seriously? Perhaps you were looking for something other than a professional encyclopedia. — Carl (CBM · talk) 12:20, 24 July 2009 (UTC)
Jokes are inappropriate for a serious encyclopedia. Paul August 12:49, 24 July 2009 (UTC)
I think some jokes can be OK, but they should not be of the sort to annoy users who are just looking for information. I'd rather have a blanket humourlessness policy that an encyclopedia filled with the sort of joke that only friends of the (ir)responsible editor will be amused by. I think that this discussion shows that the proposed joke falls firmly in the latter category. — Charles Stewart (talk) 13:18, 24 July 2009 (UTC)
I agree with CBM, Paul August, and Charles Stewart on this. I love jokes, I make a lot of jokes, however I don't find the need to plaster them everywhere. If this joke is everywhere on the net, as MarkSG states, then how is it still funny? Now if someone came up with a really fresh joke especially suited to the wikipedia format, maybe I'd reconsider, but a stale joke like this one hardly seems worthy of inclusion. RobHar (talk) 16:10, 24 July 2009 (UTC)
I'm not even saying do it in a humorous way. Just something like "As an example, see "this link" to the recursion page. That's not a joke, and the only reason in the rules not to do it is because articles don't link to themself. I think that rule can be ignored for the one page in the entire project where a self-link makes sense. Prgrmr@wrk (talk) 04:46, 26 July 2009 (UTC)
There are many better examples of recursion that we can give, though, if the goal is to explain the topic. The main point of the self-link things seems to be to pull a practical joke on readers the first time that they encounter it. But, as RobHar says, this joke has devolved into a meme. I don't see why we need to propagate that meme further (we do discuss it already in the article). — Carl (CBM · talk) 14:12, 26 July 2009 (UTC)
OK, I started this discussion, then had to go overseas for work for a while and only just got back.
I particularly am intrigued by blanket statements such as that made by Paul August above: "Jokes are inappropriate for a serious encyclopedia." Why? Says who?
The founders of this very encyclopedia didn't agree - the original page back in 2001 actually had the recursion joke in it and I remember the discussion with both Larry Sanger and Jimbo agreeing that it should be included. The recursion joke is hardly "lame or stale" - sure it may be very familiar to anyone who has studied recursion or read Douglas Hofstadtler, but it is certainly not "well-known" beyond that.
On a MUCH deeper level, I think the refusal to include it actually reflects very badly on the entire project - are we really that dour and humourless that a single joke cannot be permitted to survive? Particularly when the joke is moderately sophisticated and also explains the topic.
In light of the project receiving so much recent media attention for alienating new users, I think there is more at stake here than a simple "no jokes" ruling. Manning (talk) 07:39, 12 September 2009 (UTC)
The problem with this joke is very simple: Jokes fail when you explain them. Since this article contains a 'Humor' section to explain the joke, any instance of the joke in the article is dead on arrival. And since the Humor section also contains two examples of the joke, its presence in the See Also section would be seen not as pointless, but as amateurish. While Wikipedia doesn't need to be deadly serious all the time, it should at least have high standards. 129.229.26.125 (talk) 01:49, 19 September 2009 (UTC)
While I do greatly love this joke, my issue is that it defeats the purpose of an encyclopedia. The whole point is to provide information, and anyone who doesn't know Wikipedia will not know how to access the actual page. Now, I'm not against jokes in an encyclopedia. Taking yourself too seriously can get you into trouble. Thus, I greatly like Manning's idea of putting a link to Recursion in the See Also section. It is clever and more accurately encapsulates what recursion is. - Austin. 23:30, 5 November 2009 (UTC) —Preceding unsigned comment added by 71.88.101.229 (talk)

I went and added a recursive joke link in the format of the other uses template. Now as to why I did this.
A. Its humorous.
B. It has a very valid purpose. See WP:GRAPE for my point. The best definition of recursion IS recursion. Therefore, not including at least some unobtrusive form of a recursive example, whether it be taken as a joke or as a serious example, seems to be required, at least in my opinion.
The Application of this joke has the capability to be both funny and educational. 67.149.81.70 (talk)

It's gone now. Seems like the point about wikipedia going down hill is valid. It's sad to me that something this small can't be added without generating the controversy it has. 67.149.81.70 (talk) —Preceding undated comment added 01:51, 29 November 2009 (UTC).
Your link was labelled other definitions uses, which it wasn't, it was the same definition. The 'joke' isn't explained, and so may confuse. Wikipedia isn't a joke book. --Escape Orbit (Talk) 01:55, 29 November 2009 (UTC)
So it was an error in presentation? Would adding a termination function, or altering the presentation make it any more appropriate? I.E., something along the lines of: For an example of recursion, see Recursion ? I know this whole point seems moot, and I do recognize that wikipedia is not a joke book ((Though I would wonder if you are against articles such as All_your_base_are_belong_to_us and Badger_Badger_Badger)). However, as the Recursive humor section indicates, there is an element of wisdom in this. Furthermore, I still reference WP:GRAPE, essay or not, as a valid and logical argument for this inclusion.67.149.81.70 (talk) 02:05, 29 November 2009 (UTC)
WP:GRAPE would support a boringly literal "For an example of recursion, clicking this link will take you to this same article.", it wouldn't support a potentially confusing "See also this link" which a naive reader might assume linked to a further article about the subject. But we already have a great big section on "recursive humor", with some good jokes on the same level (and good jokes that still work if you're reading a mirror site or a physical printout). --McGeddon (talk) 10:22, 6 December 2009 (UTC)

To me, this seems sort of like if on the Rick Roll article has a citation that actually linked to a rick roll. Classless. Funny? Yea, but it doesn't go here. Nigtv (talk) 09:24, 6 December 2009 (UTC)

When I came to this page, I was upset to find that on Wikipedia, one of the best internet projects I use on a regular basis, there was no link to the recursion page on the recursion page. Wikipedia is NOT a serious business encyclopedia. Do serious business encyclopedias have a page on Lolcat? Nope! How much harm would it do to Wikipedia as a project/concept/ideal to make the word Recursion at the very beginning of the article a link to the article itself? None! And it would make me and, judging from every single person I've talked to about this, a lot of other people quite happy. Where's the harm? Why NOT? Paulcd2000 (talk) 07:53, 15 February 2010 (UTC)

Wikipedia is a serious encyclopaedia. It has articles about jokes, it quotes jokes, it explains jokes, but it doesn't make jokes. The harm in making a joke during an otherwise serious writeup is that a reader who isn't expecting a joke could be misled or confused by it - in this case, they may click the link on the assumption that it will provide further definition of the term. --McGeddon (talk) 17:26, 15 February 2010 (UTC)

I also find this joke hilarious and helpful, but perhaps inappropriate to an encyclopedia of such high caliber. I've add the joke to the Recursive humor section, where I hope it is found to be more informative as an example. ~~Andrew Keenan Richardson~~ 06:24, 24 June 2010 (UTC)

It's not really any more appropriate there. — Carl (CBM · talk) 11:28, 24 June 2010 (UTC)
A joke about recursion isn't appropriate in Recursive Humor section? It seems like that section was designed for this exact joke. ⓑⓤⓕⓐⓡ (talk) 06:24, 6 December 2010 (UTC)
The see-also-recursion joke is already explained there, at the top of the section. We add nothing to the reader's understanding by either boringly explaining "this joke would also work on Wikipedia by linking to the recursion article from the recursion article" or giggling behind our hands and saying "hey, for more information on this subject you should totally click on this link: recursion!"
Wikipedia quotes, documents and explains jokes, but it doesn't make them. --McGeddon (talk) 09:13, 6 December 2010 (UTC)


Using the principle of "Wikipedia quotes, documents and explains jokes, but it doesn't make them", as a compromise between the joke-lovers and the joke-haters, why not have a sentence along the lines of:

A hyperlink labelled "Recursion" which points to itself is regarded by some as an example of recursive humour. --Old_Wombat (talk) 11:19, 11 May 2011 (UTC)

This type of joke is already covered in the Recursive humor section. We shouldn't self-indulgently include a special Wikipedia version of the joke purely because we're on Wikipedia. --McGeddon (talk) 11:46, 4 October 2011 (UTC)
Agree. Also see WP:SELF. Paul August 11:53, 4 October 2011 (UTC)

Having just come to this article for the first time, I am disappointed that there is not a link to the article on recursion in the See Also section. I am amazed that people have actually deleted such links.81.136.210.168 (talk) 16:23, 25 May 2011 (UTC)

Let's get some quantitative rather than qualitative data - poll anyone? Casliber (talk · contribs) 11:12, 4 October 2011 (UTC)
WP:NOPOLLS. But it's already clear that plenty of editors think it'd be funny or useful to include the link. --McGeddon (talk) 11:46, 4 October 2011 (UTC)

I support having the article link to itself, and I think it can be done in a way that avoids all or most of the problems raised by those who oppose it. I agree with Prgrmr: to me, not having the link supports the image of Wikipedia as a place not to bother looking for interesting information because what you're looking for will have been deleted. While jokes are usually not included in articles, that's because they would usually be a distraction from the purpose, not because of some blanket policy against jokes; and in this case it wouldn't be a distraction, but an illustration (WP:GRAPE). To state that a joke is no longer funny is subjective -- there are those who say "funny once", and there are also many, including myself, who find some jokes funny over and over again, even sometimes funnier with each retelling. ("Oh, no. Not the Cone of Silence, Chief!") If you don't find it funny, how about just thinking of it as an unobtrusive example rather than as a joke? It can be designed so that the reader won't be confused or tricked. WP:SELF seems to me to be against saying things like "an article linking to itself, like this", but not against saying things like "a web page linking to itself", since the latter would still make perfect sense in print even if the link wouldn't be active. Coppertwig (talk) 23:25, 16 October 2011 (UTC)

WP:EGG says "make sure that the reader knows what to expect when clicking on a link" - we shouldn't have surprise wikilinks, and "linking to itself" would be expected to redirect to an article that talks about things linking to themselves. If the joke is that it's funny to click on a link without checking the URL, and then laugh when you realise you've been sent back to the recursion page, then we can only create that surprise by tricking the reader. And we should not be tricking the reader. --McGeddon (talk) 21:23, 17 October 2011 (UTC)
You're right that the reader should know what to expect when clicking; however, the point of the link is not to trick the reader. It should be worded so as to be as clear as possible. Many links on Wikipedia are ambiguous; I'm often disappointed when I click, often arriving at a page far more general than I had hoped for. We try to make them as clear as possible. If it's linked from "... or a hypertext article which links to itself" I think that's clear enough; the inclusion of the word "which" in the linking text distinguishes it from a simple link to a different article about linking to itself. (By the way, the "Recursion" article can itself reasonably be considered to be an article about things linking to themselves.) I think the point is not to create a "joke", but an illustration. You said earlier we shouldn't do it "purely because we're on Wikipedia". Here, then, are some other reasons for including it: (1) Many readers expect it. (2) Many readers want it. (3) It provides an illustrative example of recursion. (4) It enhances the article, much as an image does, creating an effect which cannot be created by text alone. (5) It follows in the footsteps of reliable sources which do the equivalent using, for example, indexes of books. WP:SELF doesn't forbid self-reference, but specifies "which types of self-references ... are acceptable". If expressed as I suggest, it would still make perfect sense when rendered on a mirror site or in print, so it meets the criteria of WP:SELF. Coppertwig (talk) 16:23, 29 October 2011 (UTC)
Many readers also do not expect this sort of thing in a professional publication. It is always a little disappointing to see in print when an author plays games by putting false items in an index (e.g. fictional people, circular "see also" entries, etc.). It would also be disappointing for us to put false items in our see also list. There is no enhancement to the article, as the link gives no more information than was already present, since the link comes back to the same article. — Carl (CBM · talk) 19:54, 29 October 2011 (UTC)
I guess it's a matter of personal preference: some perhaps find it "always a little disappointing"; others are happy to find such links and disappointed if they're not there. Coppertwig (talk) 23:20, 29 October 2011 (UTC)
Indeed. The idea of the joke occured to me yesterday and I put it in via redirect. It lasted 6 hours. I think WP would be better if it had a small number of easter eggs in it. Robert Brockway (talk) 11:36, 6 December 2011 (UTC)
I would argue that the 'joke' being discussed is not a joke, but is in fact a valid aid in understanding what recursion is. In a wikipedia page on Apple, do we not expect there to be an example of an apple? Does it not help us to understand better what an apple is. Why do we not therefore have this example of recursion? 192.68.112.171 (talk) 20:12, 23 February 2012 (UTC)
A lot of users expect exactly this sort of thing from a professional publication. I agree that in general "jokes" in encyclopedias or other reference works come off in poor taste, but it seems to be something of a tradition when it comes to "recursion." I have very rarely encountered a textbook that covers recursion in any way without its index entry for "recursion" including that page of the index. It doesn't seem to matter what the level of "seriousness" is. I personally think it would be harmless, and it would be a good show of faith that we don't have such a big chip on our shoulder about being taken seriously that we don't include the little nod that nearly every other publication does. Ltgerbilmuffin (talk) 18:52, 29 June 2012 (UTC)
So we have a bunch of people who are obsessed with keeping Wikipedia 'professional'. This isn't a business, this is Wikipedia. This is not Britannica. We are not selling Wikipedia. Complaining that it "wouldn't be professional" to have the article on recursion linking to the article on recursion is a slap in the face to countless computer science textbooks and professional works. Are you going to claim that K&R are 'unprofessional' because their book on C does it? Is Google 'unprofessional'? or do we just have an uptight view of what 'professional' means? It is also a perfect explanation of what recursion is, and therefore should not be limited to just the 'recursive humor' section. This is one of the main ways that the concept of recursion is introduced to computer science students at the undergraduate level, even at universities that are world-class research institutions. Padenton (talk) 02:51, 31 October 2012 (UTC)

FWIW, I just now came to this page for the sole purpose of seeing whether or not it had a self-reference. Numerous textbooks and Google do it, after all. TricksterWolf (talk) 02:32, 18 November 2012 (UTC)

Textbooks and Google do several things that Wikipedia articles should not do. - SudoGhost 03:24, 18 November 2012 (UTC)
You're talking about the majority of computer science textbooks, written by the most prominent computer scientists in the history of computing. Bit arrogant of you. --Padenton (talk) 21:29, 25 November 2012 (UTC)
Quoting from Wikipedia:What Wikipedia is not: Wikipedia is an encyclopedic reference, not a textbook. The purpose of Wikipedia is to present facts, not to teach subject matter. Paul August 18:59, 11 March 2013 (UTC)

I think having a recursive link to the article itself is the most visceral way of communicating the idea and is worth further discussion in this section on the talk page.108.20.48.27 (talk) 04:34, 11 March 2013 (UTC)

Difference to corecursion?[edit]

Should we discuss the difference between recursion and corecursion in this article? Tdanecker (talk) 14:58, 10 September 2009 (UTC)

I don't think so; corecursion is a relatively esoteric concept in computer science, and I don't think we should dwell on it in a general article such as this. But we should list corecursion as a see also link. — Carl (CBM · talk) 17:01, 10 September 2009 (UTC)
It probably doesn't belong here, unless we can find some applications in mathematics as well; but it could definitely get a section in Recursion (computer science). And of course, Corecursion itself is terrible and needs a lot of work. --Classicalecon (talk) 19:40, 10 September 2009 (UTC)

Programming Language[edit]

C is not necessarily the best language to describe recursion in. A functional language such as [Haskell] would appear neater and be easier to follow: for example the function for describing factorial in Haskell is:

factorial :: Int -> Int factorial 1 = 1 factorial n = n * factorial (n-1) —Preceding unsigned comment added by Abhorsen666 (talkcontribs) 01:25, 25 November 2009 (UTC)

The problem is that few people know Haskell. The C code will be readable by many people, even if they don't know C, since it is just basic imperative programming. In particular, one typical reader here is someone who is just learning to program in college; that person is not likely to learn Haskell as the first language. — Carl (CBM · talk) 01:57, 29 November 2009 (UTC)
I think that C is fine because of its simplicity and common usage. However, I'd also like to see the code written in some sort of English-like pseudo code that would make it easy to convert into whatever computing language one would like. DerekP (talk) 11:33, 6 December 2009 (UTC)

e.g.

 define function Factorial
    that receives: Integer n
    and gives:
      0 when n is less than 0.
      1 when n is less than 2.
      n times Factorial(n minus 1) when n is greater 1.
 end of definition.
I think that is harder to read than C, actually. Because I have to realize that "receives" and "gives" are supposed to be keywords in some pseudocode language, and I have to accept that the "when" structure works like it should. So I don't find that pesudocode very English-like, I find it like a functional programming language. At least C is widely known, and people can generally pretend it is any other imperative langauge without having to learn new control structures. — Carl (CBM · talk) 03:13, 4 January 2010 (UTC)
The idea was for the pseudocode to read as almost English such that one could read it out loud and, although it sounds a bit formal, it would still make sense to, say 80%, of the English-speaking population; the so-called telephone code test. There is no heavy reliance of 'keywords', just a bit of common (English) sense. However, I understand that you might be hindered by this, but I'm sure a lot of other programmers would not be, so I would still encourage its usage in Wikipedia. Anyhow, here is the equivalent C code for comparison.
 int Factorial( int n )
 {
    if (n < 0) return 0;
    if (n < 2) return 1;
    return n * Factorial(n-1);
 }

DerekP (talk) 09:31, 4 January 2010 (UTC)

That's pretty much the C code that is already in the article. But the test for negative numbers seems to be unnecessary; most people think of factorial for nonnegative numbers only, and adding a test for negative numbers just distracts from the point of demonstrating recursion. — Carl (CBM · talk) 12:43, 4 January 2010 (UTC)

How about switching to Python? It's shorter, and doesn't have types. Example code:

 def factorial(n):
   if n <= 1:
     return 1
   else:
     return n * factorial(n - 1)

This eliminates the extra lines for the braces, as well as the extra cognitive load imposed by the twice-repeated "unsigned int". I'm assuming C is more broadly known than Python, but no one who understood C could be confused about this code; and I think few people who didn't would find the C clearer. 71.198.47.81 (talk) 06:33, 21 November 2010 (UTC)

I agree with the previous comment, and intend to replace the C with Python if no one comments against that idea within a week from now. JumpDiscont (talk) 07:27, 20 September 2013 (UTC)

Section: Recursion in Language[edit]

I don't see any recursion in the Dorothy example, from the first paragraph. Can anyone explain? It doesn't have any citation either. Razvan Marinescu 16:47, 8 June 2012 (UTC) — Preceding unsigned comment added by S33us00n (talkcontribs)

Two quick points. (1) i added an internal link for 'discrete infinity' which might or might not be the correct reference (a number theory person needs to verify this for me). (2) the whole point made by chomsky about jack-built houses and wicked witches needs another two sentences to explain how it ties into the point about linguistic recursion (for example: without the ability to embed a sentence within a sentence, the concept of linguistic infinity falls apart, or whatever the point is... just needs to be made more clear). tHanks. --{{subst:User:Skychildandsonofthesun/Skychildandsonofthesun/sig2}} (talk) 11:28, 2 January 2010 (UTC)

On a different issue: nothing in Kaan & Swaab's (2002) cited paper readily lends itself to being construed as "indirect proof that Everett's ideas are wrong (...)". This sounds like somebody's personal (and somewhat odd) interpretation. Should this be changed/deleted? — Preceding unsigned comment added by Elihein (talkcontribs) 21:17, 21 January 2011 (UTC)

Deletion. I just looked at Kaan & Swaab's paper. There is nothing in there that talks about recursion. All the paper does is attempt to isolate areas of the brain that process syntax. They isolated several areas that play different rolls in processing syntax (none of which are uniquely used to process syntax anyway). They made no attempt to find a part of the brain that is hardwired for recursion. In fact, when isolating areas that process complex sentences verses simple sentences, both sentences used as examples contained recursion, it's just that the complex sentence contained a passive voice clause embedded within another clause, while the simple sentence contained an active voice clause. Grice —Preceding undated comment added 05:11, 6 December 2011 (UTC).

There is no reason for the extensive discussion of the Everett stuff in an article on linguistic recursion. That natural languages are recursive, and can be defined using recursive rules, is something that has been accepted quite widely for many years, and countless languages have proven themselves recursive. Everett has very recently started some debate on this topic, but precisely his argument is recent, widely disputed, and very rarely accepted within linguistics itself, I think it warrants—at the very most—a brief mention. It is not relevant to the question of what recursion in natural language might be. Moreover, recursion is something that comes up in semantics as well, and the current definition is focused on syntax. The standard denotation for generalized conjunction (i.e., the morpheme 'and') across categories (as in 'the dog and the cat') is recursive, in the purest mathematical sense: it's a function defined in terms of itself (the classic work on this is due to Barbara Partee and Mats Rooth, under the rubric of 'generalized conjunction'). Such recursive definitions are common in semantics. This is a foundational point about what recursion in language is. The Everett stuff, on the other hand, is just a handful of researchers making widely disputed claims about a single language that's aren't relevant to how linguistic recursion is defined (as opposed to whether it's a crosslinguistic universal). For this reason, I have reduced the Everett discussion to a brief note. I can't add the semantic stuff at the moment, but perhaps someone else may want to. MJM74 (talk) — Preceding undated comment added 00:23, 9 July 2014 (UTC)

Subject-verb agreement in first sentence?[edit]

I'm not trained in mathematics, so i'll throw out a query before adjusting grammar that might be field-specific and therefore intentional.

"specifically it is defining an infinite statement using finite component"

So i'm not sure if it should be a finite component or finite components...

but unless math has some weird way of dealing with pluralization, it's a typo in the opening sentence. —Preceding unsigned comment added by 71.224.206.164 (talk) 00:27, 16 January 2010 (UTC)

Just a curiosity...[edit]

what would happen if a redirect redirected to itself? I wouldn't do it because it'd be vandalism, but would Wikipedia allow it> —Preceding unsigned comment added by 96.253.118.75 (talk) 16:35, 17 August 2010 (UTC)

I seem to recal that there is something in the code to check the number levels of recessions, this is a safety measure so that the code does not hang. You may get a better answer at WP:VPT, also read The Difference Engine where a similar situation is a major plot element.--Salix (talk): 16:46, 17 August 2010 (UTC)

Recursion Recurring Link[edit]

I put a link to recursion on the Recursion article, because this is the definition of it. Do not delete it. IceMarioman(Talk) 23:01, 6 October 2010 (UTC)

This has been deleted, for reasons already discussed above. It's a neat and obvious joke, but it isn't appropriate for an encyclopaedia. --McGeddon (talk) 08:54, 7 October 2010 (UTC)
Aw! Coppertwig (talk) 15:58, 18 September 2011 (UTC)
It also won't work, because any links that direct to that same page becomes bold text instead. Such as: Talk:Recursion. - SudoGhost 23:28, 16 October 2011 (UTC)
It could be done via a redirect; then I think it would be blue and a real working link. Coppertwig (talk) 23:18, 29 October 2011 (UTC)

This kind of thing is nothing like a "definition"—it's merely obnoxious, especially when one doesn't know what "recursion" means, yet. If you don't already know what "recursion" means, you'll never get the joke. Besides, encyclopaedia articles require more than merely defining words. There's also the issue of citations. CüRlyTüRkeyTalkContribs 06:31, 1 November 2011 (UTC)

contests means disagrees[edit]

"Everett contests that language must have discrete infinity, and that the Pirahã language - which he claims lacks recursion - is in fact finite."

"contests" means that he disagrees; but I think the second part of the sentence is actually something Everett is asserting. (right?) so it needs to be fixed by inserting "asserts" between "and" and "that", or in some other way. Coppertwig (talk) 15:56, 18 September 2011 (UTC)

I fixed this here. Coppertwig (talk) 20:40, 11 November 2011 (UTC)

Intuitive example[edit]

I don't think that recursive procedures are hard to understand. In a family tree drawing computer program, one may implement a routine to draw a houshold of parents with their children. Recursion comes in because all parents have been children (except Adam and Eve), and all children potentially are parents. 81.207.20.42 (talk) 09:08, 6 December 2011 (UTC)

"The recursion theorem" section is poor[edit]

There are several problems with the section "The recursion theorem"

  • Its statement of the theorem is obviously false; it is written too strongly. In particular, there are obvious counter-examples of domains X and functions f : X → X where no fixed point of f exists (that is, there is no element a in X such that a = f(a), and therefore there cannot exist any F : Nat → X that has the properties described in the text). An obvious counter-example: Let X be the set of Positive Rational numbers. Let f be the function that, given a positive rational number r, returns r/2. This particular f has no fixed point, and thus shows that the statement of the Recusion Theorem provided in the article is false.
  • The provided (correctly titled) "proof of uniqueness" on the page is merely proving that if such an F exists, then it is unique. But this is not terribly useful for the purported purpose of proving that recursive definitions are meaningful, since we still need to show that such an F always exists. And as argued above, this cannot be shown, at least not with the statement of the theorem provided here.
  • The section does not link to an appropriate mathematical reference. A reader wanting to know the intended statement (rather than the written one) cannot find it directly from the section itself.
  • The most common theorems known as "The recursion theorem", such as Kleene's recursion theorem, are making much weaker claims than the one written here; but this unsurprising, since the one written here is false, while those are true. (The main difference is that Kleene's theorems are not concerned with arbitrary domains X, but rather about the domain of partial recursive functions, and showing that within that domain, recursive-definitions for total computable functions have a unique representative, and that representative can be defined as the limit point of a series of successive approximations, as one sees in Denotational semantics.)

(I am certainly not suggesting that recursively defined functions do not exist; merely that this section does more harm than good to this page.)

I am also not suggesting that we attempt to inline the text of Kleene's recursion theorem here, nor that we attempt to fix this text as it stands. Instead I suggest that the entire "The recursion theorem" be removed, and perhaps replaced with links to other articles that present the topic with the correct degree of accuracy and depth. (Failing that, then at least the statement of the theorem needs to be revised to include appropriate preconditions on the domain X and the function f.)

Pnkfelix (talk) 12:19, 19 March 2012 (UTC)

  • The statement is written correctly. You might be missing the fact that the element "a" (or, equivalently, F(0)...) is already chosen. There is no fixed point involved in defining F using f and a.
  • I agree that a reference is needed. But for the moment, i think the section's fine as it is. -- Jokes Free4Me (talk) 22:17, 20 March 2012 (UTC)
  • You're right, the non-existence of a fixed-point is not relevant here; I was misreading the conditions on F. I now see that F is just iterating f, not necessarily reaching any fixed-point. Pnkfelix (talk) 15:22, 21 March 2012 (UTC)

Chess "finite"?[edit]

"He likens it to the finite game of chess, which has a finite number of moves" Sorry, don't get this - surely a game of chess, like tennis, can continue interminably, and indeed often seems to. So the number of moves could be infinite? — Preceding unsigned comment added by 93.129.126.70 (talk) 09:25, 2 April 2012 (UTC)

At any stage in the game, the number of possible next moves is finite. Infinite sequences of moves are likely to result in an appeal to the Threefold repetition rule. Dbfirs 19:57, 26 April 2012 (UTC)
Positing that any game of chess that reaches a stale mate may result in an appeal to stop the game exacerbates the problem identified here in the article. Any real game of chess may be bounded in many ways. For instance a normal game of chess has two players, and at some time one or the other will die! More to the point though, the game can be played with the aim of not winning and not losing, and often is. The point at issue here in the article is a mathematical one and not a practical one. It concerns recursion and the notion of finite and infinite processes. In chess, at any moment, there is a finite number of moves available to a player. However the total number of POSSIBLE moves in any game is infinite. It also makes no mathematical sense to posit that as in a practice sense something is finite therefore it is not mathematically infinite. It should also be understood that there are different types of infinity for instance countable and uncountable. An example of a countable infinity is the set of ordinal numbers: 1,2,3,...etc An example of an uncountable infinity is all the numbers between 0 and 1 (or 0 and 0.01, or between etc ... so there are also an infinite number of an infinite number of ... etc etc). The number of moves possible in a chess game is an example of an uncountable infinity. This applies here to language in that while the Pirahã language may be incapable of recursion, as defined by Chomsky, that would be no reason to infer that it is less capable of infinite EXPRESSION in practice than a language that does enable the infinite EXTENSION of a single sentence in theory. LookingGlass (talk) 09:39, 27 September 2012 (UTC)

Natural numbers[edit]

We currently have two different definitions of the natural numbers in this article (one including zero and the other starting at 1). Whilst this is not really incorrect (because there really are two definitions), it might be better to use a clearly defined set such as the positive integers as the example. What does anyone else think? Dbfirs 19:37, 23 April 2012 (UTC)

Agree. Paul August 21:33, 26 April 2012 (UTC)
I see that this has now been resolved by standardising on the set of natural numbers including zero, so I'll not bother changing to the positive integers. Dbfirs 08:01, 4 May 2012 (UTC)

For all those who'd like there to be a recursion joke[edit]

Can I point out that the "See also" part of Recursion links to Strange loop, and suggest that if the "See also" from there were adjusted to link back here, that it'd be doubly appropriate - and yet at the same time entirely satisfactory to everyone who wanted to keep it serious too? (After all, mutual recursion is still an example of recursion!) 82.6.102.118 (talk) 00:03, 17 May 2012 (UTC)

Mathematical sets, recursively defined[edit]

Under: Recursion in mathematics > Recursively defined sets : Natural numbers is the following: "The set of natural numbers is the smallest set satisfying the previous two properties." The word "smallest" seems redundant to me. If there is not more than one set (and surely there should be only one set that results from the definition of any set) then the word is redundant. If there is more than one set arising from this definition of "all natural numbers", then why not choose the largest one, or any of the other sized sets that the definition gives rise to? Can anyone clarify and/or delete? LookingGlass (talk) 09:58, 27 September 2012 (UTC)

Suggestion to implement "Recursion: See Recursion" in a Wikipedia-friendly way[edit]

It's quite an interesting point - should this article contain a link to itself? That question, in and of itself, is noteworthy and probably worth including. I don't think it should because we don't do "See" lists, we do "See Also" lists, so my idea is this:

See also[edit]

Lists such as these frequently include a link to the same article, in this case Recursion, as a form of self-referential humour (see the recursive humor section).


Just an idea, in the spirit of free transmission of ideas WP exemplifies. :) 86.15.236.184 (talk) 13:04, 2 January 2013 (UTC)

I'd like to point out that this article (Recursion) points to Infinite loop, which points to Recursion (computer science), which points to Recursion, which points to Infinite loop, etc. Thus, the joke of recursion articles being recursive already exists, since it's possible to form a recursive and potentially-infinite loop through those three articles, albeit a bit indirectly. Northrupthebandgeek (talk) 22:22, 22 January 2013 (UTC)

Reoccurring Recursion Link[edit]

I always find the reoccurring discussion to add a link to link to the Wikipedia recursion article in the Wikipedia recursion article.. amusing, and reoccurring. — Preceding unsigned comment added by 212.23.25.239 (talk) 16:47, 26 June 2013 (UTC)

Wikipedia metarecursion begins with the process of adding a link to recursion to the Wikipedia article on recursion. This is then deleted by a more experienced editor, who always says it has been done before, and that it is still not funny. After some time, the person who added the link becomes a more experienced editor, and ends up removing such links and telling the new people who added them that it has been done before, and that it is still not funny. --Nigelj (talk) 12:37, 11 September 2013 (UTC)

Semi-protected edit request on 26 February 2014[edit]

Recursion/ Recursion in language

The sentence, "Dorothy, who met the Wicked Witch of the West in Munchkin Land where her sister was killed, liquidated her with a pail of water." needs a small edit. I don't know if this is a direct quote from Noam Chomsky's book, Aspects of the Theory of Syntax. 1965, but there's a comma needed after the word, "Land," as the next words, "where her sister was killed," are an appositive in this sentence. It should look like this: "Dorothy, who met the Wicked Witch of the West in Munchkin Land, where her sister was killed, liquidated her with a pail of water."

Considering this is a quote from Noam Chomsky, it's a surprisingly unclear sentence. The attempt to show recursion in language from Chomsky's point of view might need a better example, altogether. In this sentence, the recursion appears not so much a natural human construct, but a confusing obfuscation of meaning. Which person's sister was killed? The original sentence suggests it was Dorothy's sister! The appositive doesn't really clear it up, but at least suggests the possibility that it's the Wicked Witch's sister. As a tutor, I come across kids who've never heard of this story, or the movie. As incredible as that sounds, it happens. We rely on our common knowledge of this story to understand the contested sentence's meaning...but that "common" knowledge isn't as common as it once was. Also, is this story/movie seen around the world? Would a person, say, from Afghanistan know who's sister had been killed? Duse42 (talk) 20:19, 26 February 2014 (UTC)

Not done: it's not clear what changes you want made. Please mention the specific changes in a "change X to Y" format. -BZTMPS · (talk? contribs?) 22:32, 26 February 2014 (UTC)