Talk:Recursion/Archive 1

Basic Definition of Recursion

I added a basic definition of recursion to the top of the page. I trust this will satisfy the camp that likes the idea of a recursive definition of recursion, as well as those (like me) who are intimidated by immediately being hit with an obtuse, formal definition of recursion that does not tell the reader what recursion is. Robertwharvey 20:37, 28 September 2006 (UTC)

I was wondering if a simple defintion would be something like "Recursion is when something is defined, or described, in terms of itself." DerekP 09:55, 30 December 2006 (UTC)

Recursive definition of 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)

I think it's worthwhile putting a link back to recursion in the "see also" section. Any objections?

The language of the article was refreshing. And a bit of joke does no harm!210.212.160.101 13:48, 30 November 2006 (UTC)

I am presently in the hospital with plenty of time on my hands. I browsed into this article and read about halfway through. I then quickly jumped to the "see also" section hoping to find "See also, Recursion." I must say I was a bit disappointed not to find it. Just a layman's point of view (but I do recall fondly writing recursive subroutines in Pascal in college - circa 1977). I'm now going to look for a Wiki entry on "Lather, rinse, repeat." Thanks. Bruceray-jm (talk) 22:41, 25 November 2007 (UTC)

I like the link and so does my son. It should be put back. Jyarmis (talk) 02:23, 16 December 2007 (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 $X0$ (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 $X0$. 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)

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 ) , 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] 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 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:

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.

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)

What you are calling co-recursive is simply recursive. There is indeed a base case in the definition of that infinite list of ones:

• The first element of the list is 1. (the base case)
• Each element after the first is equal to the previous element. (the recursive case)

Note that if you remove the supposedly unnecessary base case, you don't have much of a definition anymore; it could be a list of 1s, of 2s, of 5s, of -32568s, of anything.

A co-recursive definition, to my knowledge, would be something like the following:

• Alpha-sorting a set of strings means sorting them first in ascending order by their first characters, then beta-sorting within those sets by the remainder of the strings.
• Beta-sorting a set of strings means sorting them first in descending order by their first characters, then alpha-sorting within those sets by the remainder of the strings.

Alpha-sorting never directly calls alpha-sorting, nor does beta-sorting directly call beta-sorting, but unless the strings are unusually short or sparse, they will call themselves, indirectly through the other. The two routines are thus co-recursive. -- Antaeus Feldspar 23:00, 25 Jun 2005 (UTC)

Your sorting example is an example of what I think is called mutual recursion, not corecursion. Such definitions can be dealt with like standard recursion. There is a problem with your analysis of the infinite list of ones. The statement "the first element of the list is 1" cannot qualify as a base case since it does not uniquely define a list. However, your analysis is not completely wrong: very many corecursive definitions can be converted to recursive definitions by a reformulation of some kind. So, for example, you could define a function which returns the nth element of the infinite list of ones using a standard recursive definition similar to your analysis. This, however, is not a list; it is a function. Anyway, I'm not the right person to add the notion of corecursion to the article, but I reiterate my request for someone to add it. --Malcohol 28 June 2005 09:46 (UTC)

I think there is a problem with your analysis of my analysis. =D No one ever said that a "base case" had to uniquely define a list, or any other complete object, in order to qualify as a base case. In order to qualify as a base case, a base case only needs to return some partial result without calling itself directly or indirectly. As well, I detect some problems with your idea that when we have created a function that exactly specifies without ambiguity or error exactly what each element of an infinite list must be, we have not "defined" that list. What, exactly, does it take to "define" a list in your view? If we state "every element in this infinite list is 1", have we not defined it? And yet that too is 'just a function', the function "f(n) = 1". -- Antaeus Feldspar 30 June 2005 00:06 (UTC)

As I don't consider myself an expert on this, I think it would be better to continue this discussion elsewhere. I've copied it to User:Malcohol/Corecursion. Everyone (especially those who know about corecursion) is invited to discuss the issue there.--Malcohol 4 July 2005 14:44 (UTC)

Surprised

I'm really surprised nobody has ever vandalized Recursion to "#redirect Recursion". - Sikon 07:42, 25 Jun 2005 (UTC)

self-link removed

This article had a link to itself at the end of the "See also" section. It was cute, but not really appropriate in my opinion, and the joke would be lost on anyone reading the article on a mirror. Besides, the same joke was also made directly above under "recursive humour." So I removed that. --Graue 21:08, 21 August 2005 (UTC)

Well, somebody has reinserted it and I endorse it. It's not a joke; it's a demonstration. Better this than the circular rd. John Reid 20:00, 26 March 2006 (UTC)

Value of ON content and quality of reference

The content added from the ON reference remains in this article, but the reference has been removed. This action is disputed and a conversation is ongoing here. Uriah923 06:47, 2 September 2005 (UTC)

Kernighan and Ritchie and the Recursive Index

Here is an interesting piece of trivia I think would be neat to add. Reading over the discussion, I figured I would bring it up for discussion instead of adding it myself.

If you look up "recursion" in the index of Kernighan and Ritchie's book, The C Programming Language, it tells you to look on page 269. . . . Page 269 is the page in the index that contains "recursion" (where you started to begin with ;).

Easter Egg (Where I found the information)

DerekP 05:48, 14 November 2005 (UTC): LOL ... Maybe, but this sounds more like an eternal loop to me than recursion. One fairly essential element of recursion is that it terminates at some point.

There's nothing essential about that. You're confusing recursion with computability. (Though I don't think the joke from K&R is that interesting or unique.) Catamorphism 06:52, 14 November 2005 (UTC)

Well maybe the joke itself isn't interesting, but the fact that Kernighan and Ritchie put into their book is interesting. These are highly respected people and a touch of humour, however lame, is a nice touch. DerekP 23:09, 15 December 2005 (UTC)

"See: Recursion" isn't a recursion imho. It's a redirection rather than a computation that uses itself. "Return: recoursion" might do, since then you don't leave the "main function" till you're done, but that's just confusing. Recursion normally takes more space as it steps forward (though it probably doesn't HAVE to) and this one doesn't. Just gives you the "intuition" that it's not recursion.

Recursion also doesn't have to terminate. When I studied scheme in the university we had infinite recoursive calculations that print and pause with every step, waiting for us to request the next step. If the basic example of recoursion is the factorial, we can define an inverse factorial that'll multiply increasing numbers, it'll be just as recoursive but will never end. AilaG 21:00, 8 May 2006 (UTC)

separated page for recursion in computer science

This papge is too crowded. I moved some content to a new page Recursion (computer science) --Leo 04:05, 12 February 2006 (UTC)

Symbol for recursion

Just as $\Sigma$ denotes summation and ${\begin{matrix}\int \end{matrix}}\,\!$ denotes integration, is there a symbol to denote recursion/iteration until the current value equals the previous one? For example:

$V=V_{o}\times {\frac {Q}{Q(V,T)}}\quad (V_{o:0}=1)\,\!$

In this situation, Q(V,T) will equal Q when V = V_o.  ~Kaimbridge~16:42, 18 February 2006 (UTC)

induction

Some parts of this article seem to equate recursion with mathematical induction, which is related but distinct. —Tamfang 22:07, 2 April 2006 (UTC)

Proof of Uniqueness

The notation in the proof uniqueness seems to be messed up. I am confused by why $f$ and $g$ are defined in English instead of with mathematical notation. $f$ takes on a different meaning $f:N\rightarrow X$ instead of $f:X\rightarrow X$. The expression

$f(n+1)=F(f(n))$

makes no sense. Why should $f(n)$ be in the domain of $F$?

I suspect that proof should look like this.

Assume

$a\in X$

$f:X\rightarrow X$

$F:N\rightarrow X$

$F(0)=a$

$F(n+1)=f(F(n))$

We show F is unique, by assuming the existance of

$G:N\rightarrow X$

where

$G(0)=a$

$G(n+1)=f(G(n))$

We want to show that $G$ must be the same function as $F$. The functions clearly have the same domain/codomain. We use induction to show that they have the same graph.

$G(0)=a=F(0)$

Assuming that

$G(n)=F(n)$

then

$G(n+1)=f(G(n))=f(F(n))=F(n+1)$

Does anyone else have an opinon about this? Josh9905When 15:37, 4 April 2006 (UTC)

Humour in the See Also?

I believe that adding Recursion to the See Also section would provide for a good chuckle, and not affect the article negatively (There is already a large "See Also" section there...) Does anyone with insight into Wikipolicy have anything to add to this? If nobody speaks up, I think I will add it myself in a week's time. toresbe 16:55, 15 November 2006 (UTC)

I agree that it is a valid inclusion. however some people don't think so, and delete it whenever someone puts it in. It was there a few days ago, someone with no sense of humour took it out. It's not worth getting into an edit war over it. Harry Mudd 16:36, 16 November 2006 (UTC)

I removed the self-link, that toresbe added. This has been discussed before, see above. I don't think the "See also" section is the appropriate place for humor, which will inevitably be confusing to some. Paul August ☎ 00:03, 27 November 2006 (UTC)

I do personally have to disagree on it being confusing.. How can it be? I sincerely cannot see any way it could detract from the understanding of the article. The only possible way it could confuse is that an editor could think it's an erroneous self-link, as you possibly did. This could be easily fixed with a comment in the Wikicode, as I should have added myself. I searched policy quite thoroughly for anything that could say that this was a no-no, and I could not find it. Harry said that it was indeed a valid inclusion, yet not worth an edit war - I quite agree, so I will wait for your approval, if any, before reinserting it. toresbe 00:12, 27 November 2006 (UTC)

I have notified the user again at his talk page. If he does not reply, I will reinsert it in a short while based on the following arguments:

• It does not detract in any noticable way from the article, and might actually aid it - or at the very least give the reader - on any skill level - a chuckle,
• For the above reason - it is not just a joke - it is a playful yet immediately and intuitively understandable example and illustration.
• Looking back in the talk page (which I neglected to do thoroughly enough previously, for which I apologize) concensus seems to be on my side.
• There seems to be nothing in policy - (Nor should there be, imnsho) which prevents humour from being part of the article, especially if it illustrates a subject and stays whithin the encyclopedic writing style,
• Several serious encyclopedi (?) have a recursive definition, and
• I will insert a comment before the link referring to the talk page so that it is not removed in good faith by a editor.

toresbe 02:56, 30 November 2006 (UTC)

Well it still seems inappropriate to me. I think it makes us look unprofessional. Out of curiosity, what are those other encyclopedias you mentioned? Paul August ☎ 03:49, 30 November 2006 (UTC)

Thanks for your reply. I respect that you may not find it appropriate - but it certainly does not detract from Wikipedias widespread credibility. The threats to Wikipedia's credibility currently mostly lie in factual accuracy, which this does not at all jeopardise. The encyclopedias I cite are all paper-form ones I've encountered through my days - but several online dictionaries and encyclopedias have them ... I'm extremely tired and about to go to bed, but I can at the very least mention Eric Raymond's consise entry -- if only because I have the JARGON file accessible via hotkeys -- which really does make you realise what recursion is in a computing sense. I've noted that you are still hesitant, but not refusing - and considering that others have spoken in favour of it, I will add it for now, with a comment in the wikicode referring to this talk page. If people are in favour of or against this this, please do not hesitate to add your two cents' worth in this paragraph. Thanks. toresbe 05:47, 30 November 2006 (UTC)

MY GOODNESS -- when making the edit, I actually realize that my link was never removed by Paul August, only that of some IP user. AAARGH!! :) All this talkpage over nothing. The link remains anyway, and I'll make a comment about the discussion here.

...I'm an idiot. :) toresbe 05:52, 30 November 2006 (UTC)

I think we need to be more mature. This is an encyclopedia, seriousness is kind of implied. I'm all for fun on Wikipedia... but not in articles. --Deskbanana 19:10, 21 December 2006 (UTC)

There is no conflict between humour and professionalism. Many major reference works have this, and it has become something of an "in joke" amongst many makers of reference works, both within corporations in internal and published word lists, and serious reference materials. This has become something of an important thing to me now :) -- and it certainly is a policy violation to revert a controvercial edit which has been discusssed and agreed upon in the talk page. toresbe 21:45, 21 February 2007 (UTC)

I think the well intentioned humor is inappropriate as it stands--all sorts of people are to read this, including wannabe overachievers like me, bright but still confusable 6th graders, people not completely fluent in English, and people in a great hurry. All of these could be confused and have their time wasted as now written. But it shouldn't be hard to make it okay with rewriting and a couple words of explanation.Rich 19:17, 21 March 2007 (UTC)

Since this approach has been used in standard reference works on recursion, if we provided a footnote mentioning this fact and supplying a source, this would appear to clear up any doubts regarding its appropriateness. I personally doubt this will confuse anyone -- In fact, I suspect sixth greaters may be particular likely to grasp and appreciate its implications. I personally don't have a problem with the article as it stands. However, putting a brief explanation and a source in a footnote should satisfy any concerns. --Shirahadasha 19:22, 21 March 2007 (UTC)

I've worked with a few 6th graders. It was astonishing to me(because I've forgotten what it was like?) how many peripheral, minor things can confuse them and get them frustrated and upset, especially the ones who're being pushed to achieve by their parents.Rich 19:35, 21 March 2007 (UTC)

Just want to repeat my support for including the self-references in this article, including both the See Also section and the References section (where I believe it is particularly appropriate to place a self-reference). There has been a long history of precedent for works in mathematics and computer science theory, both specialized and popular to contain illustrative and humorous self-references in discussions on recursion. There is no reason for Wikipedia to squelch it. Engaged readers will appreciate the touch. --Shirahadasha 21:48, 13 April 2007 (UTC)

I'd like to voice my support too -- it's an entertaining and effective demonstration of the principle, not just a joke. Andrew B Clegg 00:47, 27 July 2007 (UTC)

I'll add my voice in support as well for what it's worth. --DigitalSorceress 16:18, 21 August 2007 (UTC)

Not an acronym

See "such as GNU, PHP or TTP". I'm reluctant to change this, because there may be a set-in-stone term called recursive acronyms and I'd just bugger things up. However, I think it's bad news if we don't preserve the distinction between acronyms and initialisms. GNU, PHP and TTP cannot be said as words, so they are not acronyms (you might be able to say "Gənoo", I suppose - just!). If we lose this distinction, then we shall for ever need to say "an acronym that also spells out a word" when we wish to refer to such. It's not pedantry: it's just common sense. If everyone knows what an acronym is and what an initialism is, the language is doing its job admirably. If those who have influence over how language is presented allow words to take on different meanings (when there are already perfectly good words for those meanings), they do the language no favours. A word is weakened, not strengthened, by having more meanings, because you then have to rely on context to sort out what is meant. If context doesn't help, you're stymied, matey. Ajarmitage 08:07, 29 April 2007 (UTC)

Umm... Hello? A gnu is a wildebeest -- an African buffalo, ish. The English word is pronounced "nu" (unless you're Flanders and Swann) but it's derived from a Khoikhoi word that is indeed pronounced how you speculate. Where do you think the GNU logo comes from? If you're going to be pedantic, at least try to get it right. (Also there's a pretty good case for insisting that people who disagree with the evolution of language must voice their complaints in the style of Chaucer.) Andrew B Clegg 00:47, 27 July 2007 (UTC)

Ackermann function

Under "mathematical recursion", it says that the Ackermann function cannot be expressed without recursion. That's not true: I can write a Turing machine which calculates the Ackermann function, and Turing machines don't use recursion. Of course, Turing machines are equivalent to µ recursion and the corresponding µ-recursive function makes use of recursion, but for describing the function one can use a formalism that doesn't use recursion. --Bernhard Bauer 21:42, 16 August 2007 (UTC)

new photo?

the droste cocoa box is also the photo for the droste effect.... maybe something else could work just as well, like a screenshot of the entry.... —Preceding unsigned comment added by D Haggerty (talk • contribs) 08:23, 19 November 2007 (UTC)

problems:-

solve the followng recurrence relations:-

1. T(k)+3kTk-1)=0,T(0)=1
2. T(n)=3T(floor(n/2)),T(0)=1[ceiling function i.e. ceilin g of 8.2=8] —Preceding unsigned comment added by 59.180.182.28 (talk) 10:19, 7 December 2007 (UTC)

question

sorry if this is a silly question, but isn't the recursion described here really iteration? 69.140.152.55 (talk) 01:59, 18 May 2008 (UTC)

I think you're right. For it to be recursion, it would have to be something like:

1. Lather
2. Rinse
3. Perform the shampoo instructions

Which doesn't make a lot of sense. If you can come up with a better example, feel free to replace it. Cheers, Oliphaunt (talk) 11:50, 18 May 2008 (UTC)

Recursiveness vs. Recursivity

Which is the proper term? I notice that 'Recursiveness' is defined by Merriam Webster but gets no wikipedia results while 'Recursivity' seems to not be defined, but garners more google results and redirects to this wikipedia article. 75.144.242.225 (talk) 20:58, 18 August 2008 (UTC)

What's with the crazy "Recursive Seeking" section?

This section makes, as far as I can tell, no sense whatsoever: it's a collection of three quotations (or two quotations and a statement) without explanation. On top of that, one of the quotations is clearly missing a word. If someone feels strongly about the whole bit (and can make some sense out of it), fine, otherwise, I think it should be nuked stat. It looks like a (lame) attempt at introducing religion into the article. 66.93.135.232 (talk) 04:17, 8 September 2008 (UTC)

O.K., I'm taking it out. 66.93.135.232 (talk) 22:59, 11 September 2008 (UTC)

Different image

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?

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...

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

Difference to corecursion?

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)

Subject-verb agreement in first sentence?

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...

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

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üRkey^Talk_Contribs 06:31, 1 November 2011 (UTC)

contests means disagrees

"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

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)

Natural numbers

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)

Chess "finite"?

"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)

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

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

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).

• Corecursion
• Course-of-values recursion
• Digital infinity
• Fixed point combinator
• Infinite loop
• Infinitism
• Iterated function
• Mise en abyme
• etc.

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)

Semi-protected edit request on 26 February 2014

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)

Mathematical sets, recursively defined

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)

Found the following on StackOverflow by Imp:

(1) 1 is a natural number`
(2) If N is a natural number, than N+1 is a natural number as well

This is an implication, not an equivalence. What this says is - if for 
any number these conditions hold, it is a natural number. It says nothing 
about whether there are other natural numbers.

(3) N is the smallest set satisfying (1) and (2)

This says precisely that the first two conditions are exhausting. Not 
only every number that satisfies them is natural, but also - any number 
that does not, is not natural.

The condition (3) could also be rephrased as

Every natural number can be obtained by a finite number of applications 
of (2) on (1)

or simply

Nothing else is a natural number

Sounds good, especially that last sentence. Propose adding something to this effect. LookingGlass (talk) 14:42, 5 November 2014 (UTC)

Bourton-on-the-Water's model model model model village

Should this page include a reference to Bourton-on-the-Water? That village has a model village, which includes a model model village, which includes a model model model village, which includes a model model model model village. See this article for pictures. SnappingTurtle (talk) 20:18, 13 April 2015 (UTC)

Think this would be reasonable to include in the "In art" section, as another example of physical 3D recursion. --Mark viking (talk) 21:10, 13 April 2015 (UTC)

... but only if there is a reliable source for this claim. Having visited Bourton-on-the-Water model village, I am sceptical about the reality of this "model model model model village". There is indeed a model model village, and a model model model village is just about credible, but any further levels of recursion would be microscopic. Gandalf61 (talk) 13:31, 14 April 2015 (UTC)

Well, there's a photo in the ref above. It says, "Look closely near the top left corner - that's a "model model model model village"". Are you saying you think the photo is photoshopped and it's all a massive hoax? --Nigelj (talk) 20:06, 14 April 2015 (UTC)

The photo is not very clear. All I'm saying is that someone's holiday snaps are not a reliable source as defined in Wikipedia. Gandalf61 (talk) 16:18, 16 April 2015 (UTC)

This photo from the Metro news site shows three levels of recursion clearly enough, and the prose also says it is a Grade II heritage site, giving it some notability. --Mark viking (talk) 16:53, 16 April 2015 (UTC)

This is only a 'fun fact'. I don't see why you're setting the bar of WP:V verifiability so high? It's not as if we'd be claiming anything extraordinary. It seems perfectly obvious from all the photographs that this is an example of physical recursion in an artwork. We don't even have a citation for the existing Russian Doll example. Are you planning on contesting it until a scholarly paper can be found to verify that too? --Nigelj (talk) 23:10, 16 April 2015 (UTC)

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

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)

When I saw the section titled "Recursive humor" I was really hoping to find the old "Pete and Repeat were sitting in a boat. Pete fell out. Who was left? [Repeat.] Pete and Repeat were sitting in a boat. Pete fell out..."  :) VenusGx (talk) 20:11, 24 November 2015 (UTC)

"The recursion theorem" section is poor

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)

The proof of the recursion theorem is a usual gap in undergrad math courses as it is strangely difficult. In my site on the foundations of maths I offer a relatively simple solution by a more general result giving the existence of interpretations of terms and term algebras in any algebraic language (the "well-foundedness" there simply comes down to the induction axiom in the case of ℕ as a term {0,S}-algebra).Spoirier (talk) 03:54, 18 June 2016 (UTC)

Definition of recursion in lead

The definition appear to be incorrect.

"Recursion is the process of repeating items in a self-similar way."

Sorry, what? That would seem to be saying that a production line is recursive. No, it isn't.

This so called 'definition' is unreferenced and untenable.

The next sentence claims that 'For instance, when the surfaces of two mirrors are exactly parallel with each other, the nested images that occur are a form of infinite recursion.' IMO the infinity mirror pattern probably could easily be defined in terms of recursion, but again, it's unreferenced, and OR.

This article seems to be subject to pathological editting patterns. I notice that even adding a request for a reference has been revert warred away already.GliderMaven (talk) 02:28, 2 July 2016 (UTC)

I'm pretty sure that self-similarity is not part of a definition of recursion, self-similarity is characteristic of fractals not recursion (fractals can be generated by recursion, but that doesn't mean that recursion is self-similar, that's a logical error). However, 'self-reference' is characteristic of recursion.GliderMaven (talk) 02:40, 2 July 2016 (UTC)

Reoccurring Recursion Link

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)

Actually, it is funny, it's just not encyclopedic. Paul August ☎ 16:29, 12 July 2017 (UTC)

not a recurrence relation

Some common recurrence relations are:

• Golden Ratio: $\phi =1+(1/\phi )=1+(1/(1+(1/(1+1/...))))$

Er no. There is no sequence of golden numbers each of which is defined by its predecessor(s). I removed that example. —Tamfang (talk) 08:39, 5 December 2017 (UTC)

What about phi(0)=1, phi(n+1)=1/(1+phi(n))? — Charles Stewart (talk) 08:46, 5 December 2017 (UTC)

The limit can be expressed using a fixpoint operator in a non-computable extension to the reals: mu X.1/(1+X). — Charles Stewart (talk) 09:44, 5 December 2017 (UTC) edited

That's nice I'm sure. —Tamfang (talk) 16:58, 5 December 2017 (UTC)

As it stands, the entry says nothing about such a sequence. Your phi(n) is a Fibonacci ratio, and the Fibonacci numbers are in that same list, so what would this add? —Tamfang (talk) 21:06, 5 December 2017 (UTC)

Semi-protected edit request on 18 December 2017

Under "Recursive humor," fix the "GNU" link so it links to the correct GNU, rather than GNU project. RedPanda3226 (talk) 00:59, 18 December 2017 (UTC)

Done Gulumeemee (talk) 03:37, 18 December 2017 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Recursion. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20050206051223/http://www.freenetpages.co.uk/hp/alan.gauld/tutrecur.htm to http://www.freenetpages.co.uk/hp/alan.gauld/tutrecur.htm

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 18 January 2022).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 00:22, 13 January 2018 (UTC)