HOME

TheInfoList




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 language, meaning that it is a comprehensive, systematic, objective, and precise study of language. Linguistics encompasses the analysis of every aspect of language, as well as the methods for studying ...

linguistics
to
logic Logic is an interdisciplinary field which studies truth and reasoning. Informal logic seeks to characterize Validity (logic), valid arguments informally, for instance by listing varieties of fallacies. Formal logic represents statements and ar ...

logic
. The most common application of recursion is in
mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and their changes (cal ...
and
computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of , , and . Computer science ...
, where a
function Function or functionality may refer to: Computing * Function key A function key is a key on a computer A computer is a machine that can be programmed to carry out sequences of arithmetic or logical operations automatically. Modern comp ...
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 can occur.


Formal definitions

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, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is, F_0=0,\quad F_1= 1, and F_n= ...

Fibonacci sequence
is another classic example of recursion: : as base case 1, : as base case 2, :For all
integer An integer (from the Latin Latin (, or , ) is a classical language belonging to the Italic branch of the Indo-European languages. Latin was originally spoken in the area around Rome, known as Latium. Through the power of the Roman Re ...
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 total order, ordering (as in "this is the ''third'' largest city in the country"). In common mathematical terminology, w ...
s by the
Peano axioms In mathematical logic Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical pr ...
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 Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no g ...
s,
function Function or functionality may refer to: Computing * Function key A function key is a key on a computer A computer is a machine that can be programmed to carry out sequences of arithmetic or logical operations automatically. Modern comp ...
s (e.g.,
recurrence relation In mathematics, a recurrence relation is an equation that expresses the ''n''th term of a sequence (mathematics), sequence as a function (mathematics), function of the ''k'' preceding terms, for some fixed ''k'' (independent from ''n''), which is ca ...
s), sets (e.g.,
Cantor ternary set In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
), and
fractal In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities a ...

fractal
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 Linguistics is the science, scientific study of language. It e ...
.


Informal definition

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. 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 linguist Linguistics is the scientific study of language A language is a structured system of communication used by humans, including speech (spoken language), gesture ...

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 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. Recently, however, the generally accepted idea that recursion is an essential property of human language has been challenged by
Daniel Everett Daniel Leonard Everett (born 1951) is an American linguist Linguistics is the scientific study of language A language is a structured system of communication used by humans, including speech (spoken language), gestures (Signed langua ...
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 Amazonas () is a States of Brazil, state of Brazil, located in the North Region, Brazil, North Region ...
. Andrew Nevins, David Pesetsky and Cilene Rodrigues are among many who have argued against this. Literary
self-reference Self-reference occurs in natural language, natural or formal languages when a Sentence (linguistics), sentence, idea or Well-formed formula, formula refers to itself. The reference may be expressed either directly—through some intermediate s ...
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, wikt:σημαντικός, σημαντικός ''sēmantikós'', "significant") is the study of reference, Meaning (philosophy), meaning, or truth. The term can be used to refer to subfields of several distinct discipline ...
. 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 grammarIn computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of Algorith ...
is a formal grammar that contains recursive production rules..


Recursive humor

Recursion is sometimes used humorously in computer science, programming, philosophy, or mathematics textbooks, generally by giving a
circular definition A circular definition is a definition A definition is a statement of the meaning of a term (a word In linguistics, a word of a spoken language can be defined as the smallest sequence of phonemes that can be uttered in isolation with s ...
or
self-reference Self-reference occurs in natural language, natural or formal languages when a Sentence (linguistics), sentence, idea or Well-formed formula, formula refers to itself. The reference may be expressed either directly—through some intermediate s ...
, 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 becaus ...

infinite regress
. 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 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 megastructure in the ''Halo'' series ...
of some editions of
Brian Kernighan Brian Wilson Kernighan (; born 1942) is a Canadian computer scientist A computer scientist is a person A person (plural people or persons) is a being that has certain capacities or attributes such as reason, morality, consciousness or self- ...
and
Dennis Ritchie Dennis MacAlistair Ritchie (September 9, 1941 – October 12, 2011) was an American . He created the and, with long-time colleague , the and . Ritchie and Thompson were awarded the from the in 1983, the from the in 1990 and the from in ...

Dennis Ritchie
's book ''
The C Programming Language ''The C Programming Language'' (sometimes termed ''K&R'', after its authors' initials) is a computer programming Computer programming is the process of designing and building an executable computer program to accomplish a specific computing r ...
''; 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 Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of , ...
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 u ...

Andrew Plotkin
: ''"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 Cognitive science is the interdisciplinary Interdisciplinarity or interdisciplinary studies involves the combination of two or more academic ...
than you are; then ask him or her what recursion is."''
Recursive acronym A recursive acronym is an acronym An acronym is a word or name formed from the initial components of a longer name or phrase, usually using individual initial letters, as in NATO (North Atlantic Treaty Organization) or European Union, EU (Europ ...
s are other examples of recursive humor.
PHP PHP is a general-purpose scripting language A scripting language or script language is a programming language A programming language is a formal language comprising a Instruction set architecture, set of instructions that produce various k ...

PHP
, for example, stands for "PHP Hypertext Preprocessor",
WINE Wine is an alcoholic drink typically made from Fermentation in winemaking, fermented grapes. Yeast in winemaking, Yeast consumes the sugar in the grapes and converts it to ethanol and carbon dioxide, releasing heat in the process. Different ...
stands for "WINE Is Not an Emulator"
GNU GNU () is an extensive collection of free software Free software (or libre software) is computer software distributed under terms that allow users to run the software for any purpose as well as to study, change, and distribute it and any ...

GNU
stands for "GNU's not Unix", and
SPARQL SPARQL (pronounced " sparkle" , a recursive acronym A recursive acronym is an acronym An acronym is a word or name formed from the initial components of a longer name or phrase, usually using individual initial letters, as in NATO (North ...
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 total order, ordering (as in "this is the ''third'' largest city in the country"). In common mathematical terminology, w ...

natural numbers
: :0 is in \mathbb :if ''n'' is in \mathbb, then ''n'' + 1 is in \mathbb :The set of natural numbers is the smallest set satisfying the previous two properties. In mathematical logic, the
Peano axioms In mathematical logic Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical pr ...
(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 abstract algebra (particularly ring theory In algebra, ring theory is the study of ring (mathematics), rings ...
and by the Italian mathematician
Giuseppe Peano Giuseppe Peano (; ; 27 August 1858 – 20 April 1932) was an Italian mathematician A mathematician is someone who uses an extensive knowledge of mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as ...

Giuseppe Peano
. 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 Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
that are defined in terms of a
proof procedureIn logic Logic (from Ancient Greek, Greek: grc, wikt:λογική, λογική, label=none, lit=possessed of reason, intellectual, dialectical, argumentative, translit=logikḗ)Also related to (''logos''), "word, thought, idea, argument, acc ...
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 remarkable and deep properties. It was discovered in 1874 by Henry John Stephen Smith and introduced by German mathematician Georg Cantor in 1883 ...

Cantor set
is a subdivision rule, as is
barycentric subdivision In geometry, the barycentric subdivision is a standard way of dividing an arbitrary convex polygon into triangles, a convex polyhedron into tetrahedron, tetrahedra, or, in general, a convex polytope into simplex, simplices with the same dimension, b ...

barycentric subdivision
.


Functional recursion

A
function Function or functionality may refer to: Computing * Function key A function key is a key on a computer A computer is a machine that can be programmed to carry out sequences of arithmetic or logical operations automatically. Modern comp ...
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 In , a sequence is an enumerated collection of in which repetitions are allowed and matters. Like a , it contains (also called ''elements'', or ''terms''). The numbe ...

Fibonacci number
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 Computability theory, also known as recursion theory, is a branch of mathematical logic Mathematical logic, also called formal logic, is a subfield of mathematics Mathematics (from Ancient Greek, Greek: ) includes t ...
, which, unlike the Fibonacci sequence, cannot be expressed without recursion.


Proofs involving recursive definitions

Applying the standard technique of
proof by cases Proof by exhaustion, also known as proof by cases, proof by case analysis, complete induction or the brute force method, is a method of mathematical proof A mathematical proof is an Inference, inferential Argument-deduction-proof distinctions, a ...
to recursively defined sets or functions, as in the preceding sections, yields
structural inductionStructural induction is a proof method that is used in mathematical logic Mathematical logic, also called formal logic, is a subfield of mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (num ...
— a powerful generalization of
mathematical induction Mathematical induction can be informally illustrated by reference to the sequential effect of falling dominoes. Mathematical induction is a mathematical proof A mathematical proof is an Inference, inferential Argument-deduction-proof distinct ...
widely used to derive proofs in
mathematical logic Mathematical logic is the study of 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 formal sys ...
and computer science.


Recursive optimization

Dynamic programming Dynamic programming is both a mathematical optimization File:Nelder-Mead Simionescu.gif, Nelder-Mead minimum search of Test functions for optimization, Simionescu's function. Simplex vertices are ordered by their values, with 1 having the lo ...
is an approach to
optimization File:Nelder-Mead Simionescu.gif, Nelder-Mead minimum search of Test functions for optimization, Simionescu's function. Simplex vertices are ordered by their values, with 1 having the lowest ( best) value., alt= Mathematical optimization (alter ...
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 (mathematics), optimization method known as dynamic programming. It writes the "value" of a decision problem ...
, 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 that studies , 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 , is mostly concerned with those that are relevant to ...
, 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 F: \N \to X (where \N denotes the set of natural numbers including zero) such that :F(0) = a :F(n + 1) = f(F(n)) for any natural number .


Proof of uniqueness

Take two functions F: \N \to X and G: \N \to X such that: :F(0) = a :G(0) = a :F(n + 1) = f(F(n)) :G(n + 1) = f(G(n)) where is an element of . It can be proved by
mathematical induction Mathematical induction can be informally illustrated by reference to the sequential effect of falling dominoes. Mathematical induction is a mathematical proof A mathematical proof is an Inference, inferential Argument-deduction-proof distinct ...
that for all natural numbers : :Base Case: so the equality holds for . :Inductive Step: Suppose for some Then . ::Hence implies . By induction, for all n \in \N.


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 designing and building an executable computer program to accomplish a specific computing result or to perform a particular task. Programming involves tasks such as analysis, generating algorithms, Profilin ...
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 File:Nelder-Mead Simionescu.gif, Nelder-Mead minimum search of Test functions for optimization, Simionescu's function. Simplex vertices are ordered by their values, with 1 having the lo ...
. 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 Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no g ...
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 Base or BASE may refer to: Brands and enterprises *Base (mobile telephony provider), a Belgian mobile telecommunications operator *Base CRM, an enterprise software company founded in 2009 with offices in Mountain View and Kraków, Poland *Base De ...
, 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 of , either in , or s, conforming to the rules of a . The term ''parsing'' comes from Latin ''pars'' (''orationis''), meaning . The term has slightly different meani ...

parser
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 Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no gener ...
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 Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities an ...
). 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 .


In art

The Russian Doll or
Matryoshka doll Matryoshka dolls ( rus, матрёшка, p=mɐˈtrʲɵʂkə, a=Ru-матрёшка.ogg; also known as babushka dolls, stacking dolls, nesting dolls, Russian tea dolls, or Russian dolls) are a set of wooden dolls of decreasing size placed one ...
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 A mononymous person is an individual who is known and addressed by a single name, or mononym. In some cases, that name has been selected by the individual, who may have originally ...

Giotto
's '' Stefaneschi Triptych'', made in 1320. Its central panel contains the kneeling figure of Cardinal Stefaneschi, holding up the triptych itself as an offering. M. C. Escher'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 Linguistics is the science, scientific study of language. It e ...

recursive
ly contains the picture, and so ''
ad infinitum ''Ad infinitum'' is a Latin Latin (, or , ) is a classical language belonging to the Italic languages, Italic branch of the Indo-European languages. Latin was originally spoken in the area around Rome, known as Latium. Through the power of the ...

ad infinitum
''.


See also

*
Corecursion In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of Algori ...
*
Course-of-values recursion In computability theory Computability theory, also known as recursion theory, is a branch of mathematical logic Mathematical logic, also called formal logic, is a subfield of mathematics Mathematics (from Ancient Greek, Greek: ) includes t ...
*
Digital infinityDigital infinity is a technical term in theoretical linguistics Theoretical linguistics is a term in linguistics which, like the related term general linguistics, can be understood in different ways. Both can be taken as a reference to theory of lang ...
* A Dream Within a Dream (poem) *
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, creating a loop which theoretic ...

Droste effect
*
False awakening A false awakening is a vivid and convincing dream A dream is a succession of images, idea In philosophy Philosophy (from , ) is the study of general and fundamental questions, such as those about reason, Metaphysics, existence, E ...
* Fixed point combinator *
Infinite compositions of analytic functionsIn mathematics, infinite compositions of analytic function In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry) ...
*
Infinite loop In computer programming Computer programming is the process of designing and building an executable computer program to accomplish a specific computing result or to perform a particular task. Programming involves tasks such as analysis, ge ...
*
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 becaus ...

Infinite regress
*
Infinitism Infinitism is the view that knowledge may be justified by an infinite chain of reasons. It belongs to epistemology Epistemology (; ) is the Outline of philosophy, branch of philosophy concerned with knowledge. Epistemologists study the natur ...
*
Infinity mirror Infinity represents something that is boundless or endless, or else something that is larger than any real number, real or natural number. It is often denoted by the infinity symbol shown here. Since the time of the Greek mathematics, ancient ...
*
Iterated function In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and th ...
*
Mathematical induction Mathematical induction is a mathematical proof technique. It is essentially used to prove that a statement ''P''(''n'') holds for every natural number ''n'' = 0, 1, 2, 3, . . . ; that is, the overall statement is a ...
*
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 ...

Mise en abyme
*
Reentrant (subroutine) In computing Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processes and development of both computer hardware , hardware and softwar ...
*
Self-reference Self-reference occurs in natural language, natural or formal languages when a Sentence (linguistics), sentence, idea or Well-formed formula, formula refers to itself. The reference may be expressed either directly—through some intermediate s ...
*
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 vo ...
* Strange loop *
Tail recursion In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of Algorit ...
* Tupper's self-referential formula *
Turtles all the way down "Turtles all the way down" is an expression of the problem of 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 i ...

Turtles all the way down


References


Bibliography

* * * * * * * - offers a treatment of
corecursion In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of Algori ...
. * * * * *, 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