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

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

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

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

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

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

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

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

: ''"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 ...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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