Talk:Recursion

From Wikipedia, the free encyclopedia

Mathematics Portal

This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.

Mathematics rating:

B Class

Mid Priority

Field: Foundations, logic, and set theory

One of the 500 most frequently viewed mathematics articles.

Please update this rating as the article progresses, or if the rating is inaccurate. Click to show/hide comments.
Please add to or update the comments to suggest improvements to the article.
Geometry guy 21:03, 17 June 2007 (UTC)

[edit] 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)

[edit] 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

X 0

(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

X 0

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

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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:

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

[edit] 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)

[edit] 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)

[edit] Surprised

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

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] Symbol for recursion

Just as $Σ$ 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)

[edit] 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)

[edit] 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)

[edit] 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. --Desk banana 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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:

Lather
Rinse
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)