Talk:Recursion/Archive 2

This is an archive of past discussions about Recursion. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page.

Archive 1

Archive 2

Semi-protected edit request on 18 January 2018

This edit request to Recursion has been answered. Set the |answered= parameter to no to reactivate your request.

The paragraph before the contents end as follows:

where a function being defined is applied within its own definition. While this apparently defines an infinite number of instances (function values), it is often done in such a way that no loop or infinite chain of references can occur.

the last part of the last sentence that reads "no loop or infinite chain of references can occur" is not clear. I suggest that we remove the word "loop" altogether and restate it as "no infinite chain of self references can occur". Owino (talk) 13:40, 18 January 2018 (UTC)

Not done: An Infinite loop is described lower in the article. Spintendo ᔦᔭ 15:05, 18 January 2018 (UTC)

Edit request

I think that Center embedding should be added to the See Also section. 169.228.157.89 (talk) 03:02, 19 January 2018 (UTC)

Sloppy caption edit skirmish

The woman in this image holds an object that contains a smaller image of her holding an identical object, which in turn—at least conceptually, if not in resolvable pigment—contains a smaller image of herself holding an identical object, and so forth.

User:Joel B. Lewis just reverted my change in bold. He describes himself on his talk page as a mathematician, but seems not to realize that a painting is not a set: mathematical sets being nearly the only object where we take unlimited recursion seriously. (Gödel, Escher, Bach has a high time with René Magritte's "this is not a pipe".)

Nearly every other form of mooted recursion is exponentially degradational. Even in computer science, recursion is not a panacea in working systems. (It's nice in formal design, but there we're back again to mathematics again.)

In linguistics, languages are theoretically recursive, but you can barely find any natural utterances (out of trillions) where the recursive depth can't be counted on one hand (in English, you start to sound stiff, wonky, roundabout, or formal by the time you get to three).

I think it's a rudeness and disservice to the reader to be unclear about the distinction between conceptual recursion and practical recursion, but I only made this edit in passing, and this is my final two cents on the subject. — MaxEnt 14:08, 4 March 2018 (UTC)

What is rude here is the unwarranted and baseless personal remark in your edit: please strike it. What is a disservice to the reader to over-burden a clear and well-made point in an image caption with irrelevant and uninteresting asides. No one has ever been confused about whether there *really are* infinitely many cocoa tins on that one cocoa tin. --JBL (talk) 14:27, 4 March 2018 (UTC)

Semi-protected edit request on 7 June 2018

This edit request to Recursion has been answered. Set the |answered= parameter to no to reactivate your request.

Makes the first or second word of recursion a link to itself. Guymanforget (talk) 16:29, 7 June 2018 (UTC)

Not done: Amusing, but unencyclopedic. And also done multiple times before. ‑‑ElHef (Meep?) 16:41, 7 June 2018 (UTC)

Semi-protected edit request on 20 October 2018

Wanted to add reference for Everett's 2005 paper

Everett, D. 2005, "Cultural Constraints on Grammar and Cognition in Pirahã: Another Look at the Design Features of Human Language", Current Anthropology, vol. 46, no. 4, pp. 621-646.

And possibly his response to Nevins, Pesetsky, and Rodrigues.
Everett, D.L. 2009, "Piraha Culture and Grammar: A Response to Some Criticisms", Language, vol. 85, no. 2, pp. 405.

But then I suppose N,P, & R's response to his response should be cited as well....
Nevins, A., Pesetsky, D. & Rodrigues, C. 2009, "Evidence and argumentation: A reply to Everett (2009)", Language, vol. 85, no. 3, pp. 671.

There is also this paper:
Futrell, R., Stearns, L., Everett, D.L., Piantadosi, S.T. & Gibson, E. 2016, "A Corpus Investigation of Syntactic Embedding in Pirahã", PLoS One, vol. 11, no. 3, pp. e0145289.

So perhaps just his 2005 paper!

(I'm looking into this topic as I consider the language dependence of universal classification schemes) 2.31.134.66 (talk) 12:09, 20 October 2018 (UTC)

how about a section on film since there is one on art?

Its a very popular trope in film, groundhog Day, Synecdoche New York etc etc — Preceding unsigned comment added by 222.152.243.85 (talk) 09:22, 12 March 2019 (UTC)

Provable propositions

I removed the following paragraph: ″in non-constructive approaches to the foundations of mathematics, the set of true propositions may be larger than the set inductively defined from the axioms and rules of inference. See also Gödel's incompleteness theorems.

For the following reasons: The fact that a proof method might be incomplete (as it is the case with second-order logic) is not the issue here. The fact that an axiomatic system (like Peano Arithmetic) might5 be incomplete (as has been established by Gödel's First Incompleteness Theorem) is not the issue here.

The issue of an article on recursion is that in mathematical logic, proofs are formalized as recursive functions or relations. There is also, in my opinion, no need to raise the philosophical issue of how provability in a formal system relates to truth in an article on recursion. — Preceding unsigned comment added by Bbbaat (talk • contribs) 07:25, 10 June 2019 (UTC)

I agree. --JBL (talk) 11:31, 10 June 2019 (UTC)

Programming Language

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 (talk • contribs) 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 agree. C and similarly structured languages such as C++, JavaScript, C#, Java, etc... are pretty much a de facto standard for code examples.

Steinm07 (talk) 19:43, 21 July 2019 (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)

Layman's question

Pls forgive me for asking a general question which may not be relevant to the article ... I might have found the answer if I already knew it ... but - starting out with "definition by higher genus and lower species" - is there a higher genus or class of phenomena that encompasses recursion (like recursion can be said to encompass self-reference)? Like ... is there a general phenomenon of, say "things that work upon themselves", which then might include e.g. physics, at least on the lower level of mechanics? And if not, is there a criterion for excluding these or similar types of phenomena? TiA! T 85.166.160.249 (talk) 04:57, 12 October 2019 (UTC)

Another example of recursion in art

The YouTuber, cyriak, has plenty of recursive elements in his surreal music videos. I don't have the ability (yet) to edit semi-protected pages though. May I request help adding this in? — Preceding unsigned comment added by Aarondeobell (talk • contribs) 12:06, 5 July 2020 (UTC)

Is there a reliable, secondary source that mentions this? Many people use recursion in various ways, but unless there is a quality source that discusses it, it won't be appropriate to include. --JBL (talk) 12:18, 5 July 2020 (UTC)

In cyriak's Know Your Meme page, he's specifically tagged with "recursion". He has a post on the Recursion subreddit. and his 1.5 million subscriber channel has an intro video with recursive elements that are as obvious as shown in the art of the wiki. And as a bonus, this popular meme, whose humor is entirely based on the premise of recursion, has an article that specifically mentions "recursive". Man, I need semi-protected privileges! Thank you very much for your time :D — Preceding unsigned comment added by Aarondeobell (talk • contribs) 12:50, 5 July 2020 (UTC)

Please see the page WP:RS that I linked in my previous comment: none of these are "reliable sources" in the sense that is relevant here. (I put these words in quotation marks because the meaning of the words in the context of Wikipedia is not necessarily what one would expect -- you can see more details at the link. The subsection on Questionable and self-published sources is particularly relevant.) All the other examples in that section are sourced to academic or museum sources.
In order to be able to edit semi-protected pages, all that is required is to have an account for sufficiently long and make sufficiently many contributions to Wikipedia articles. However, if your edits are things like adding unsourced content, or content sourced to websites like knowyourmeme, then it is likely that someone will revert them fairly quickly. --JBL (talk) 13:40, 5 July 2020 (UTC)

Section: Recursion in Language

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 (talk • contribs)

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 (talk • contribs) 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)

Came across this article where the author explains the structure of the English language and how it relates to Recursive Thinking. Found this really helpful to understand the concept of Recursion in Computer Science applied to a subject I am already competent in. I'm a new contributor (2 edits in so far) - am submitting an edit Request to add this to the list of resources at the bottom. Link: https://www.americanscientist.org/article/the-uniqueness-of-human-recursive-thinking EchoRashmi (talk) 21:09, 18 September 2020 (UTC)^[1]

References

[1]
https://www.americanscientist.org/article/the-uniqueness-of-human-recursive-thinking

Recursive Definition Compromise

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)

Actually, I think the compromise is reasonable and would be appreciated by users. It gets away from the question of whether the simple "recursion: see recursion" joke is now officially lame, it provides a good, simple answer, and it doesn't even have to be thought of as a joke. But even if it were a joke, I firmly believe there is no reason to believe an encyclopedia can never have them (other than "because I say so"), but (and this might be the point Paul August and others are really trying to make, it should not lower the tone by going too far, and it should certainly not have bogus entries (like Maori drums) for any silly reason. But it can remain a trustworthy, respected reference and still have something like "For a practical example, see: recursion", and that is what we're all after, surely. Maitchy (talk) 00:45, 1 April 2016 (UTC)

I think the best way to settle this is to provide this link where it is topical, and that is in the recursive humor section.Regicide1 (talk) 17:11, 27 October 2020 (UTC)

I know why this page is semi-protected.

Add learnrecursion.com to the recursion humor section

Recursion in Giotto's Stefaneschi Triptych

The article currently has a {{failed verification}} tag for the following statement: Recursion has been used in paintings since Giotto's Stefaneschi Triptych, made in 1320. Its central panel contains the kneeling figure of Cardinal Stefaneschi, holding up the triptych itself as an offering. The reference clearly supports the second part of this (quote: "cardinal Stefaneschi, holding in his hands the model of the triptych"). What it does not directly support is the connection to recursion, which is not mentioned in the source (as pointed out by JayBeeEll in this edit).
However, the article does mention the Droste effect; and in that article (which has good article status), a similar claim is made in the lead section and in the paragraph about medieval art. Do we need a source that connects the Triptych explicitly to recursion, or do we even have to make changes to the Droste effect article? Renerpho (talk) 23:24, 1 April 2022 (UTC)

I too would be interested in hearing other editors' views about whether I am being overly pedantic about this. --JBL (talk) 14:17, 3 April 2022 (UTC)

@JayBeeEll: To be honest, I mostly agree with your revert. Which is to say, if you are overly pedantic then so am I. The Triptych looks like a nice example for recursion, until you realize that nobody seems to make that connection independently of the two Wikipedia articles (this one, and the Droste effect article). I don't like that, at all! Renerpho (talk) 10:03, 6 April 2022 (UTC)

Are there any reliable sources calling this an example of recursion that do not lead back to Wikipedia? I'm not saying it is (yet), but if this turns out to be a WP:REFLOOP, that would be quite funny, actually... Renerpho (talk) 10:08, 6 April 2022 (UTC)

@Renerpho and JayBeeEll: We don't necessarily need a source that connects the Triptych explicitly to recursion, a source citing the Triptych as an example of the Droste effect would seem to be sufficient, for example: Svozil p. 12 Paul August ☎ 11:10, 6 April 2022 (UTC)

Yes, I agree, that would be fine. --JBL (talk) 11:21, 6 April 2022 (UTC)

Agreed. I've replaced the {{failed verification}} tag with that new source. Renerpho (talk) 23:33, 20 April 2022 (UTC)