Recursion

Recursion occurs when the definition of a concept or process depends on a simpler or previous version of itself.

The most common application of recursion is in mathematics and computer science, where a function being defined is applied within its own definition.

Linguist Noam Chomsky, among many others, has argued that the lack of an upper bound on the number of grammatical sentences in a language, and the lack of an upper bound on grammatical sentence length (beyond practical constraints such as the time available to utter one), can be explained as the consequence of recursion in natural language.

This provides a way of understanding the creativity of language—the unbounded number of grammatical sentences—because it immediately predicts that sentences can be of arbitrary length: Dorothy thinks that Toto suspects that Tin Man said that....

In order to provide a single denotation for it that is suitably flexible, and is typically defined so that it can take any of these different types of meanings as arguments.

[10] Recursion is sometimes used humorously in computer science, programming, philosophy, or mathematics textbooks, generally by giving a circular definition or self-reference, in which the putative recursive step does not get closer to a base case, but instead leads to an infinite regress.

It is not unusual for such books to include a joke entry in their glossary along the lines of: A variation is found on page 269 in the index of some editions of Brian Kernighan and Dennis Ritchie's book The C Programming Language; the index entry recursively references itself ("recursion 86, 139, 141, 182, 202, 269").

Early versions of this joke can be found in Let's talk Lisp by Laurent Siklóssy (published by Prentice Hall PTR on December 1, 1975, with a copyright date of 1976) and in Software Tools by Kernighan and Plauger (published by Addison-Wesley Professional on January 11, 1976).

Another interesting example is the set of all "provable" propositions in an axiomatic system that are defined in terms of a proof procedure which is inductively (or recursively) defined as follows: Finite subdivision rules are a geometric form of recursion, which can be used to create fractal-like images.

Applying the standard technique of proof by cases to recursively defined sets or functions, as in the preceding sections, yields structural induction — a powerful generalization of mathematical induction widely used to derive proofs in mathematical logic and computer science.

In set theory, this is a theorem guaranteeing that recursively defined functions exist.

by recursion, and gave a sketch of an argument in the 1888 essay "Was sind und was sollen die Zahlen?"

As a computer programming technique, this is called divide and conquer and is key to the design of many important algorithms.

Recursion in computer programming is exemplified when a function is defined in terms of simpler, often smaller versions of itself.

The great advantage of recursion is that an infinite set of possible sentences, designs or other data can be defined, parsed or produced by a finite computer program.

Some specific kinds of recurrence relation can be "solved" to obtain a non-recursive definition (e.g., a closed-form expression).

The main disadvantage is that the memory usage of recursive algorithms may grow very quickly, rendering them impractical for larger instances.

Authors use the concept of recursivity to foreground the situation in which specifically social scientists find themselves when producing knowledge about the world they are always already part of.

[17][18] According to Audrey Alejandro, “as social scientists, the recursivity of our condition deals with the fact that we are both subjects (as discourses are the medium through which we analyse) and objects of the academic discourses we produce (as we are social agents belonging to the world we analyse).”[19] From this basis, she identifies in recursivity a fundamental challenge in the production of emancipatory knowledge which calls for the exercise of reflexive efforts:we are socialised into discourses and dispositions produced by the socio-political order we aim to challenge, a socio-political order that we may, therefore, reproduce unconsciously while aiming to do the contrary.

The recursivity of our situation as scholars – and, more precisely, the fact that the dispositional tools we use to produce knowledge about the world are themselves produced by this world – both evinces the vital necessity of implementing reflexivity in practice and poses the main challenge in doing so.Recursion is sometimes referred to in management science as the process of iterating through levels of abstraction in large business entities.

Its central panel contains the kneeling figure of Cardinal Stefaneschi, holding up the triptych itself as an offering.

[23][24] This practice is more generally known as the Droste effect, an example of the Mise en abyme technique.