![Droste Cacao Alcalinise blikje, foto4](https://upload.wikimedia.org/wikipedia/commons/d/d9/Droste_Cacao_Alcalinise_blikje%2C_foto4.JPG)
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from
linguistics
Linguistics is the scientific study of human language. It is called a scientific study because it entails a comprehensive, systematic, objective, and precise analysis of all aspects of language, particularly its nature and structure. Linguis ...
to
logic
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premises ...
. The most common application of recursion is in
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
and
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, where a
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
being defined is applied within its own definition. While this apparently defines an infinite number of instances (function values), it is often done in such a way that no infinite loop or infinite chain of references ("crock recursion") can occur.
Formal definitions
![Serpiente alquimica](https://upload.wikimedia.org/wikipedia/commons/7/71/Serpiente_alquimica.jpg)
In mathematics and computer science, a class of objects or methods exhibits recursive behavior when it can be defined by two properties:
* A simple ''base case'' (or cases) — a terminating scenario that does not use recursion to produce an answer
* A ''recursive step'' — a set of rules that reduces all successive cases toward the base case.
For example, the following is a recursive definition of a person's ''ancestor''. One's ancestor is either:
*One's parent (''base case''), ''or''
*One's parent's ancestor (''recursive step'').
The
Fibonacci sequence
In mathematics, the Fibonacci numbers, commonly denoted , form a integer sequence, sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start ...
is another classic example of recursion:
: as base case 1,
: as base case 2,
:For all
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s , .
Many mathematical axioms are based upon recursive rules. For example, the formal definition of the
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''Cardinal n ...
s by the
Peano axioms
In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly ...
can be described as: "Zero is a natural number, and each natural number has a successor, which is also a natural number." By this base case and recursive rule, one can generate the set of all natural numbers.
Other recursively defined mathematical objects include
factorial
In mathematics, the factorial of a non-negative denoted is the product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial:
\begin
n! &= n \times (n-1) \times (n-2) \t ...
s,
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
s (e.g.,
recurrence relation
In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...
s),
sets (e.g.,
Cantor ternary set
In mathematics, the Cantor set is a set of points lying on a single line segment that has a number of unintuitive properties. It was discovered in 1874 by Henry John Stephen Smith and introduced by German mathematician Georg Cantor in 1883.
Thr ...
), and
fractal
In mathematics, a fractal is a geometric shape containing detailed structure at arbitrarily small scales, usually having a fractal dimension strictly exceeding the topological dimension. Many fractals appear similar at various scales, as illu ...
s.
There are various more tongue-in-cheek definitions of recursion; see
recursive humor
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
.
Informal definition
![Sourdough](https://upload.wikimedia.org/wikipedia/commons/0/0a/Sourdough.jpg)
Recursion is the process a procedure goes through when one of the steps of the procedure involves invoking the procedure itself. A procedure that goes through recursion is said to be 'recursive'.
To understand recursion, one must recognize the distinction between a procedure and the running of a procedure. A procedure is a set of steps based on a set of rules, while the running of a procedure involves actually following the rules and performing the steps.
Recursion is related to, but not the same as, a reference within the specification of a procedure to the execution of some other procedure.
When a procedure is defined as such, this immediately creates the possibility of an endless loop; recursion can only be properly used in a definition if the step in question is skipped in certain cases so that the procedure can complete. Recursion comes in three forms: ''direct'', ''indirect'', and ''circular''. Direct recursion is when a function (A) invokes itself (A references A); indirect recursion occurs when one function (A) invokes (B), function (B) invokes function (C), function (C) invokes (D), etc., until one of the functions in the chain invokes an earlier one. Circular recursion occurs when function (A) and function (B) invoke each other. If an infinite loop occurs in direct, indirect, or circular recursion, it is said to be the condition of "crock recursion." There are basically two ways to prevent crock recursion, either limit the number of times a function may reference itself, or place an absolute limit on the depth of function calls, e.g. if there is a depth limit of 50, any time a procedure calls another, a counter is increased; when it exits, that counter is decreased. Once the counter reaches the limit (in this case, 50) no further procedure calls are allowed; if any attempt to call a 51st function is made, the operation is terminated. Using a recursion limit prevents only crock recursion; placing a call limit, in addition to halting crock recursion, may have the side effect of preventing the execution of legitimate complex procedures which are deeply nested, but not recursive.
But even if it is properly defined, a recursive procedure is not easy for humans to perform, as it requires distinguishing the new from the old, partially executed invocation of the procedure; this requires some administration as to how far various simultaneous instances of the procedures have progressed. For this reason, recursive definitions are very rare in everyday situations.
In language
Linguist
Noam Chomsky
Avram Noam Chomsky (born December 7, 1928) is an American public intellectual: a linguist, philosopher, cognitive scientist, historian, social critic, and political activist. Sometimes called "the father of modern linguistics", Chomsky is ...
, 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 can be understood in terms of a recursive definition of a syntactic category, such as a sentence. A sentence can have a structure in which what follows the verb is another sentence: ''Dorothy thinks witches are dangerous'', in which the sentence ''witches are dangerous'' occurs in the larger one. So a sentence can be defined recursively (very roughly) as something with a structure that includes a noun phrase, a verb, and optionally another sentence. This is really just a special case of the mathematical definition of recursion.
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...''. There are many structures apart from sentences that can be defined recursively, and therefore many ways in which a sentence can embed instances of one category inside another. Over the years, languages in general have proved amenable to this kind of analysis.
The generally accepted idea that recursion is an essential property of human language has been challenged by
Daniel Everett
Daniel Leonard Everett (born 26 July 1951) is an American linguist and author best known for his study of the Amazon basin's Pirahã people and their language.
Everett is currently Trustee Professor of Cognitive Sciences at Bentley University i ...
on the basis of his claims about the
Pirahã language
Pirahã (also spelled ''Pirahá, Pirahán''), or Múra-Pirahã, is the indigenous language of the isolated Pirahã people of Amazonas, Brazil. The Pirahã live along the Maici River, a tributary of the Amazon River.
Pirahã is the only surviving ...
. Andrew Nevins, David Pesetsky and Cilene Rodrigues are among many who have refuted this challenge. Literary
self-reference
Self-reference occurs in natural or formal languages when a sentence, idea or formula refers to itself. The reference may be expressed either directly—through some intermediate sentence or formula—or by means of some encoding. In philoso ...
can in any case be argued to be different in kind from mathematical or logical recursion.
Recursion plays a crucial role not only in syntax, but also in
natural language semantics
Semantics (from grc, σημαντικός ''sēmantikós'', "significant") is the study of reference, meaning, or truth. The term can be used to refer to subfields of several distinct disciplines, including philosophy, linguistics and comput ...
. The word ''and'', for example, can be construed as a function that can apply to sentence meanings to create new sentences, and likewise for noun phrase meanings, verb phrase meanings, and others. It can also apply to intransitive verbs, transitive verbs, or ditransitive verbs. 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. This can be done by defining it for a simple case in which it combines sentences, and then defining the other cases recursively in terms of the simple one.
A
recursive grammar In computer science, a grammar is informally called a recursive grammar if it contains production rules that are recursive, meaning that expanding a non-terminal according to these rules can eventually lead to a string that includes the same non-te ...
is a formal grammar that contains recursive
production rules.
[.]
Recursive humor
![Web Page](https://upload.wikimedia.org/wikipedia/commons/b/bd/Web_Page.png)
Recursion is sometimes used humorously in computer science, programming, philosophy, or mathematics textbooks, generally by giving a
circular definition
A circular definition is a description that uses the term(s) being defined as part of the description or assumes that the term(s) being described are already known. There are several kinds of circular definition, and several ways of characteris ...
or
self-reference
Self-reference occurs in natural or formal languages when a sentence, idea or formula refers to itself. The reference may be expressed either directly—through some intermediate sentence or formula—or by means of some encoding. In philoso ...
, in which the putative recursive step does not get closer to a base case, but instead leads to an
infinite regress
An infinite regress is an infinite series of entities governed by a recursive principle that determines how each entity in the series depends on or is produced by its predecessor. In the epistemic regress, for example, a belief is justified beca ...
. It is not unusual for such books to include a joke entry in their glossary along the lines of:
:Recursion, ''see Recursion''.
A variation is found on page 269 in the
index
Index (or its plural form indices) may refer to:
Arts, entertainment, and media Fictional entities
* Index (''A Certain Magical Index''), a character in the light novel series ''A Certain Magical Index''
* The Index, an item on a Halo megastru ...
of some editions of
Brian Kernighan
Brian Wilson Kernighan (; born 1942) is a Canadian computer scientist.
He worked at Bell Labs and contributed to the development of Unix alongside Unix creators Ken Thompson and Dennis Ritchie. Kernighan's name became widely known through co-au ...
and
Dennis Ritchie
Dennis MacAlistair Ritchie (September 9, 1941 – October 12, 2011) was an American computer scientist. He is most well-known for creating the C programming language and, with long-time colleague Ken Thompson, the Unix operating system and B p ...
's book ''
The C Programming Language
''The C Programming Language'' (sometimes termed ''K&R'', after its authors' initials) is a computer programming book written by Brian Kernighan and Dennis Ritchie, the latter of whom originally designed and implemented the language, as well as ...
''; 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). The joke also appears in ''The UNIX Programming Environment'' by Kernighan and Pike. It did not appear in the first edition of ''The C Programming Language''. The joke is part of the
Functional programming
In computer science, functional programming is a programming paradigm where programs are constructed by Function application, applying and Function composition (computer science), composing Function (computer science), functions. It is a declar ...
folklore and was already widespread in the functional programming community before the publication of the aforementioned books.
Another joke is that "To understand recursion, you must understand recursion."
[ In the English-language version of the Google web search engine, when a search for "recursion" is made, the site suggests "Did you mean: ''recursion''." An alternative form is the following, from ]Andrew Plotkin
Andrew Plotkin (born May 15, 1970), also known as Zarf, is a central figure in the modern interactive fiction (IF) community. Having both written a number of award-winning games and developed a range of new file formats, interpreters, and other ...
: ''"If you already know what recursion is, just remember the answer. Otherwise, find someone who is standing closer to Douglas Hofstadter
Douglas Richard Hofstadter (born February 15, 1945) is an American scholar of cognitive science, physics, and comparative literature whose research includes concepts such as the sense of self in relation to the external world, consciousness, an ...
than you are; then ask him or her what recursion is."''
Recursive acronym
A recursive acronym is an acronym that refers to itself, and appears most frequently in computer programming. The term was first used in print in 1979 in Douglas Hofstadter's book '' Gödel, Escher, Bach: An Eternal Golden Braid'', in which Hof ...
s are other examples of recursive humor. PHP
PHP is a general-purpose scripting language geared toward web development. It was originally created by Danish-Canadian programmer Rasmus Lerdorf in 1993 and released in 1995. The PHP reference implementation is now produced by The PHP Group ...
, for example, stands for "PHP Hypertext Preprocessor", WINE
Wine is an alcoholic drink typically made from fermented grapes. Yeast consumes the sugar in the grapes and converts it to ethanol and carbon dioxide, releasing heat in the process. Different varieties of grapes and strains of yeasts are m ...
stands for "WINE Is Not an Emulator" GNU
GNU () is an extensive collection of free software (383 packages as of January 2022), which can be used as an operating system or can be used in parts with other operating systems. The use of the completed GNU tools led to the family of operat ...
stands for "GNU's not Unix", and SPARQL
SPARQL (pronounced "sparkle" , a recursive acronym for SPARQL Protocol and RDF Query Language) is an RDF query language—that is, a semantic query language for databases—able to retrieve and manipulate data stored in Resource Description F ...
denotes the "SPARQL Protocol and RDF Query Language".
In mathematics
Recursively defined sets
Example: the natural numbers
The canonical example of a recursively defined set is given by the natural numbers
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''cardinal n ...
:
:0 is in
:if ''n'' is in , then ''n'' + 1 is in
:The set of natural numbers is the smallest set satisfying the previous two properties.
In mathematical logic, the Peano axioms
In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly ...
(or Peano postulates or Dedekind–Peano axioms), are axioms for the natural numbers presented in the 19th century by the German mathematician Richard Dedekind
Julius Wilhelm Richard Dedekind (6 October 1831 – 12 February 1916) was a German mathematician who made important contributions to number theory, abstract algebra (particularly ring theory), and
the axiomatic foundations of arithmetic. His ...
and by the Italian mathematician Giuseppe Peano
Giuseppe Peano (; ; 27 August 1858 – 20 April 1932) was an Italian mathematician and glottologist. The author of over 200 books and papers, he was a founder of mathematical logic and set theory, to which he contributed much notation. The stand ...
. The Peano Axioms define the natural numbers referring to a recursive successor function and addition and multiplication as recursive functions.
Example: Proof procedure
Another interesting example is the set of all "provable" propositions in an axiomatic system
In mathematics and logic, an axiomatic system is any set of axioms from which some or all axioms can be used in conjunction to logically derive theorems. A theory is a consistent, relatively-self-contained body of knowledge which usually contai ...
that are defined in terms of a proof procedure In logic, and in particular proof theory, a proof procedure for a given logic is a systematic method for producing proofs in some proof calculus of (provable) statements.
Types of proof calculi used
There are several types of proof calculi. The mo ...
which is inductively (or recursively) defined as follows:
*If a proposition is an axiom, it is a provable proposition.
*If a proposition can be derived from true reachable propositions by means of inference rules, it is a provable proposition.
*The set of provable propositions is the smallest set of propositions satisfying these conditions.
Finite subdivision rules
Finite subdivision rules are a geometric form of recursion, which can be used to create fractal-like images. A subdivision rule starts with a collection of polygons labelled by finitely many labels, and then each polygon is subdivided into smaller labelled polygons in a way that depends only on the labels of the original polygon. This process can be iterated. The standard `middle thirds' technique for creating the Cantor set
In mathematics, the Cantor set is a set of points lying on a single line segment that has a number of unintuitive properties. It was discovered in 1874 by Henry John Stephen Smith and introduced by German mathematician Georg Cantor in 1883.
Thr ...
is a subdivision rule, as is barycentric subdivision
In mathematics, the barycentric subdivision is a standard way to subdivide a given simplex into smaller ones. Its extension on simplicial complexes is a canonical method to refine them. Therefore, the barycentric subdivision is an important tool i ...
.
Functional recursion
A function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
may be recursively defined in terms of itself. A familiar example is the Fibonacci number
In mathematics, the Fibonacci numbers, commonly denoted , form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start the sequence from ...
sequence: ''F''(''n'') = ''F''(''n'' − 1) + ''F''(''n'' − 2). For such a definition to be useful, it must be reducible to non-recursively defined values: in this case ''F''(0) = 0 and ''F''(1) = 1.
A famous recursive function is the Ackermann function
In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total computable function that is not primitive recursive. All primitive recursive functions are total ...
, which, unlike the Fibonacci sequence, cannot be expressed without recursion.
Proofs involving recursive definitions
Applying the standard technique of proof by cases to recursively defined sets or functions, as in the preceding sections, yields structural induction Structural induction is a proof method that is used in mathematical logic (e.g., in the proof of Łoś' theorem), computer science, graph theory, and some other mathematical fields. It is a generalization of mathematical induction over natural num ...
— a powerful generalization of mathematical induction
Mathematical induction is a method for proving that a statement ''P''(''n'') is true for every natural number ''n'', that is, that the infinitely many cases ''P''(0), ''P''(1), ''P''(2), ''P''(3), ... all hold. Informal metaphors help ...
widely used to derive proofs in mathematical logic
Mathematical logic is the study of logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of for ...
and computer science.
Recursive optimization
Dynamic programming
Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics.
I ...
is an approach to optimization
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...
that restates a multiperiod or multistep optimization problem in recursive form. The key result in dynamic programming is the Bellman equation
A Bellman equation, named after Richard E. Bellman, is a necessary condition for optimality associated with the mathematical optimization method known as dynamic programming. It writes the "value" of a decision problem at a certain point in time ...
, which writes the value of the optimization problem at an earlier time (or earlier step) in terms of its value at a later time (or later step).
The recursion theorem
In set theory
Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly conce ...
, this is a theorem guaranteeing that recursively defined functions exist. Given a set , an element of and a function , the theorem states that there is a unique function (where denotes the set of natural numbers including zero) such that
:
:
for any natural number .
Proof of uniqueness
Take two functions and such that:
:
:
:
:
where is an element of .
It can be proved by mathematical induction
Mathematical induction is a method for proving that a statement ''P''(''n'') is true for every natural number ''n'', that is, that the infinitely many cases ''P''(0), ''P''(1), ''P''(2), ''P''(3), ... all hold. Informal metaphors help ...
that for all natural numbers
:
:Base Case: so the equality holds for .
:Inductive Step: Suppose for some Then .
::Hence implies .
By induction, for all .
In computer science
A common method of simplification is to divide a problem into subproblems of the same type. As a computer programming
Computer programming is the process of performing a particular computation (or more generally, accomplishing a specific computing result), usually by designing and building an executable computer program. Programming involves tasks such as ana ...
technique, this is called divide and conquer and is key to the design of many important algorithms. Divide and conquer serves as a top-down approach to problem solving, where problems are solved by solving smaller and smaller instances. A contrary approach is dynamic programming
Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics.
I ...
. This approach serves as a bottom-up approach, where problems are solved by solving larger and larger instances, until the desired size is reached.
A classic example of recursion is the definition of the factorial
In mathematics, the factorial of a non-negative denoted is the product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial:
\begin
n! &= n \times (n-1) \times (n-2) \t ...
function, given here in C code:
unsigned int factorial(unsigned int n)
The function calls itself recursively on a smaller version of the input and multiplies the result of the recursive call by , until reaching the base case, analogously to the mathematical definition of factorial.
Recursion in computer programming is exemplified when a function is defined in terms of simpler, often smaller versions of itself. The solution to the problem is then devised by combining the solutions obtained from the simpler versions of the problem. One example application of recursion is in parser
Parsing, syntax analysis, or syntactic analysis is the process of analyzing a string of symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal grammar. The term ''parsing'' comes from Lati ...
s for programming languages. 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.
Recurrence relation
In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...
s are equations which define one or more sequences recursively. Some specific kinds of recurrence relation can be "solved" to obtain a non-recursive definition (e.g., a closed-form expression
In mathematics, a closed-form expression is a mathematical expression that uses a finite number of standard operations. It may contain constants, variables, certain well-known operations (e.g., + − × ÷), and functions (e.g., ''n''th roo ...
).
Use of recursion in an algorithm has both advantages and disadvantages. The main advantage is usually the simplicity of instructions. The main disadvantage is that the memory usage of recursive algorithms may grow very quickly, rendering them impractical for larger instances.
In biology
Shapes that seem to have been created by recursive processes sometimes appear in plants and animals, such as in branching structures in which one large part branches out into two or more similar smaller parts. One example is Romanesco broccoli
Romanesco broccoli (also known as Roman cauliflower, Broccolo Romanesco, Romanesque cauliflower, Romanesco or broccoflower) is an edible flower bud of the species ''Brassica oleracea''. It is chartreuse in color, and has a form naturally approx ...
.
In art
The Russian Doll or Matryoshka doll
Matryoshka dolls ( ; rus, матрёшка, p=mɐˈtrʲɵʂkə, a=Ru-матрёшка.ogg), also known as stacking dolls, nesting dolls, Russian tea dolls, or Russian dolls, are a set of wooden dolls of decreasing size placed one inside ano ...
is a physical artistic example of the recursive concept.
Recursion has been used in paintings since Giotto
Giotto di Bondone (; – January 8, 1337), known mononymously as Giotto ( , ) and Latinised as Giottus, was an Italian painter and architect from Florence during the Late Middle Ages. He worked during the Gothic/Proto-Renaissance period. Giot ...
's ''Stefaneschi Triptych
The ''Stefaneschi Altarpiece'' is a triptych by the Italian painter Giotto (c. 1267 – 1337), commissioned by Cardinal (Catholicism), Cardinal Giacomo Gaetani Stefaneschi to serve as an altarpiece for one of the altars of Old St. Peter's Ba ...
'', made in 1320. Its central panel contains the kneeling figure of Cardinal Stefaneschi, holding up the triptych itself as an offering. This practice is more generally known as the Droste effect
The Droste effect (), known in art as an example of ''mise en abyme'', is the effect of a picture recursively appearing within itself, in a place where a similar picture would realistically be expected to appear. This produces a loop which in ...
, an example of the Mise en abyme
In Western art history, ''mise en abyme'' (; also ''mise en abîme'') is a formal technique of placing a copy of an image within itself, often in a way that suggests an infinitely recurring sequence. In film theory and literary theory, it refers t ...
technique.
M. C. Escher
Maurits Cornelis Escher (; 17 June 1898 – 27 March 1972) was a Dutch graphic artist who made mathematically inspired woodcuts, lithographs, and mezzotints.
Despite wide popular interest, Escher was for most of his life neglected in t ...
's '' Print Gallery'' (1956) is a print which depicts a distorted city containing a gallery which recursive
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
ly contains the picture, and so ''ad infinitum
''Ad infinitum'' is a Latin phrase meaning "to infinity" or "forevermore".
Description
In context, it usually means "continue forever, without limit" and this can be used to describe a non-terminating process, a non-terminating ''repeating'' pro ...
''.
See also
* Corecursion
In computer science, corecursion is a type of operation that is dual to recursion. Whereas recursion works analytically, starting on data further from a base case and breaking it down into smaller data and repeating until one reaches a base case, ...
* Course-of-values recursion
In computability theory, course-of-values recursion is a technique for defining number-theoretic functions by recursion. In a definition of a function ''f'' by course-of-values recursion, the value of ''f''(''n'') is computed from the sequence \lan ...
* Digital infinity Digital infinity is a technical term in theoretical linguistics. Alternative formulations are "discrete infinity" and "the infinite use of finite means". The idea is that all human languages follow a simple logical principle, according to which a li ...
* A Dream Within a Dream (poem)
"A Dream Within a Dream" is a poem written by American poet Edgar Allan Poe, first published in 1849. The poem has 24 lines, divided into two stanzas. Analysis
The poem dramatizes the confusion felt by the narrator as he watches the important th ...
* Droste effect
The Droste effect (), known in art as an example of ''mise en abyme'', is the effect of a picture recursively appearing within itself, in a place where a similar picture would realistically be expected to appear. This produces a loop which in ...
* False awakening
A false awakening is a vivid and convincing dream about awakening from sleep, while the dreamer in reality continues to sleep. After a false awakening, subjects often dream they are performing daily morning routine such as showering, cooking, cl ...
* Fixed point combinator
In mathematics and computer science in general, a '' fixed point'' of a function is a value that is mapped to itself by the function.
In combinatory logic for computer science, a fixed-point combinator (or fixpoint combinator) is a higher-order f ...
* Infinite compositions of analytic functions
In mathematics, infinite compositions of analytic functions (ICAF) offer alternative formulations of analytic continued fractions, series, products and other infinite expansions, and the theory evolving from such compositions may shed light on the ...
* Infinite loop
In computer programming, an infinite loop (or endless loop) is a sequence of instructions that, as written, will continue endlessly, unless an external intervention occurs ("pull the plug"). It may be intentional.
Overview
This differs from:
* ...
* Infinite regress
An infinite regress is an infinite series of entities governed by a recursive principle that determines how each entity in the series depends on or is produced by its predecessor. In the epistemic regress, for example, a belief is justified beca ...
* Infinitism
Infinitism is the view that knowledge may be justified by an infinite chain of reasons. It belongs to epistemology, the branch of philosophy that considers the possibility, nature, and means of knowledge.
Epistemological infinitism
Since Gettie ...
* Infinity mirror
The infinity mirror (also sometimes called an infinite mirror) is a configuration of two or more parallel or nearly parallel mirrors, creating a series of smaller and smaller reflections that appear to recede to infinity. Often the front mirror ...
* Iterated function
In mathematics, an iterated function is a function (that is, a function from some set to itself) which is obtained by composing another function with itself a certain number of times. The process of repeatedly applying the same function is ...
* Mathematical induction
Mathematical induction is a method for proving that a statement ''P''(''n'') is true for every natural number ''n'', that is, that the infinitely many cases ''P''(0), ''P''(1), ''P''(2), ''P''(3), ... all hold. Informal metaphors help ...
* Mise en abyme
In Western art history, ''mise en abyme'' (; also ''mise en abîme'') is a formal technique of placing a copy of an image within itself, often in a way that suggests an infinitely recurring sequence. In film theory and literary theory, it refers t ...
* Reentrant (subroutine)
In computing, a computer program or subroutine is called reentrant if multiple invocations can safely run concurrently on multiple processors, or on a single processor system, where a reentrant procedure can be interrupted in the middle of its exe ...
* Self-reference
Self-reference occurs in natural or formal languages when a sentence, idea or formula refers to itself. The reference may be expressed either directly—through some intermediate sentence or formula—or by means of some encoding. In philoso ...
* Spiegel im Spiegel
' ( 'mirror(s) in the mirror') is a composition by Arvo Pärt written in 1978, just before his departure from Estonia. The piece is in the '' tintinnabular'' style, wherein a ''melodic voice'', operating over diatonic scales, and ''tintinnabular ...
* Strange loop
A strange loop is a cyclic structure that goes through several levels in a hierarchical system. It arises when, by moving only upwards or downwards through the system, one finds oneself back where one started.
Strange loops may involve self-refe ...
* Tail recursion
In computer science, a tail call is a subroutine call performed as the final action of a procedure. If the target of a tail is the same subroutine, the subroutine is said to be tail recursive, which is a special case of direct recursion. Tail recur ...
* Tupper's self-referential formula
Tupper's self-referential formula is a formula that visually represents itself when graphed at a specific location in the (''x'', ''y'') plane.
History
The formula was defined by Jeff Tupper and appears as an example in Tupper's 2001 SIGGRAP ...
* Turtles all the way down
References
Bibliography
*
*
*
*
*
*
* - offers a treatment of corecursion
In computer science, corecursion is a type of operation that is dual to recursion. Whereas recursion works analytically, starting on data further from a base case and breaking it down into smaller data and repeating until one reaches a base case, ...
.
*
*
*
*
*, first chapter on set theory.
External links
Recursion
- tutorial by Alan Gauld
Nevins, Andrew and David Pesetsky and Cilene Rodrigues. Evidence and Argumentation: A Reply to Everett (2009). Language 85.3: 671--681 (2009)
{{Authority control
Theory of computation
Self-reference
Feedback
Articles with example C code