**Recursion** is the process of repeating items in a

self-similarIn mathematics, a self-similar object is exactly or approximately similar to a part of itself . Many objects in the real world, such as coastlines, are statistically self-similar: parts of them show the same statistical properties at many scales...

way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from

linguisticsLinguistics is the scientific study of human language. Linguistics can be broadly broken into three categories or subfields of study: language form, language meaning, and language in context....

to

logicIn philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...

. The most common application of recursion is in

mathematicsMathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

and

computer scienceComputer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

, in which it refers to a method of defining

functionsIn mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...

in which the function being defined is applied within its own definition. Specifically this defines an infinite number of instances (function values), using a finite expression that for some instances may refer to other instances, but in such a way that no loop or infinite chain of references can occur. The term is also used more generally to describe a process of repeating objects in a self-similar way.

## Formal definitions of recursion

In

mathematicsMathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

and

computer scienceComputer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

, a class of objects or methods exhibit recursive behavior when they can be defined by two properties:

- A simple base case (or cases), and
- A set of rules which reduce all other cases toward the base case.

For example, the following is a recursive definition of a person's ancestors:

- One's parent
A parent is a caretaker of the offspring in their own species. In humans, a parent is of a child . Children can have one or more parents, but they must have two biological parents. Biological parents consist of the male who sired the child and the female who gave birth to the child...

s are one's ancestorAn ancestor is a parent or the parent of an ancestor ....

s (*base case*).
- The parents of one's ancestors are also one's ancestors (
*recursion step*).

The Fibonacci sequence is a classic example of recursion:

- Fib(0) is 0 [base case]
- Fib(1) is 1 [base case]
- For all integers n > 1: Fib(n) is (Fib(n-1) + Fib(n-2)) [recursive definition]

Many mathematical axioms are based upon recursive rules. For example, the formal definition of the

natural numberIn mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...

s in

set theorySet theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...

follows:

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

A more humorous illustration goes:

*"To understand recursion, you must first understand recursion."* Or perhaps more accurate is the following, from

Andrew PlotkinAndrew Plotkin , also known as Zarf, is a central figure in the modern interactive fiction community. Having both written a number of award-winning games and developed a range of new file formats, interpreters, and other utilities for the design, production, and running of IF games, Plotkin is...

:

*"If you already know what recursion is, just remember the answer. Otherwise, find someone who is standing closer to Douglas Hofstadter*Douglas Richard Hofstadter is an American academic whose research focuses on consciousness, analogy-making, artistic creation, literary translation, and discovery in mathematics and physics...

than you are; then ask him or her what recursion is."
Recursively defined mathematical objects include

functionIn mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...

s, sets, and especially

fractalA fractal has been defined as "a rough or fragmented geometric shape that can be split into parts, each of which is a reduced-size copy of the whole," a property called self-similarity...

s.

## Recursion in language

Linguist

Noam ChomskyAvram Noam Chomsky is an American linguist, philosopher, cognitive scientist, and activist. He is an Institute Professor and Professor in the Department of Linguistics & Philosophy at MIT, where he has worked for over 50 years. Chomsky has been described as the "father of modern linguistics" and...

theorizes that unlimited extension of a language such as

EnglishEnglish is a West Germanic language that arose in the Anglo-Saxon kingdoms of England and spread into what was to become south-east Scotland under the influence of the Anglian medieval kingdom of Northumbria...

is possible using the recursive device of embedding phrases within sentences. Thus, a chatty person may say,

*"Dorothy, who met the wicked Witch of the West in Munchkin Land where her wicked Witch sister was killed, liquidated her with a pail of water."* Clearly, two simple sentences—

*"Dorothy met the Wicked Witch of the West in Munchkin Land"* and

*"Her sister was killed in Munchkin Land"*—can be embedded in a third sentence,

*"Dorothy liquidated her with a pail of water,"* to obtain a very verbose sentence.

The idea that recursion is an essential property of human language (as Chomsky suggests) is challenged by

linguistLinguistics is the scientific study of human language. Linguistics can be broadly broken into three categories or subfields of study: language form, language meaning, and language in context....

Daniel EverettDaniel Leonard Everett is a U.S. author and academic best known for his study of the Amazon Basin's Pirahã people and their language....

in his work

*Cultural Constraints on Grammar and Cognition in Pirahã: Another Look at the Design Features of Human Language*, in which he hypothesizes that cultural factors made recursion unnecessary in the development of the

Pirahã languagePirahã is a language spoken by the Pirahã. The Pirahã are an indigenous people of Amazonas, Brazil, living along the Maici River, a tributary of the Amazon....

. This concept, which challenges Chomsky's idea that recursion is the only trait which differentiates human and animal communication, is currently under debate.

Andrew Nevins, David Pesetsky and Cilene Rodrigues provide a debate against this proposal. Indirect proof that Everett's ideas are wrong comes from works in neurolinguistics where it appears that all human beings are endowed with the very same neurobiological structures to manage with all and only recursive languages. For a review, see Kaan et al. (2002)

Recursion in linguistics enables 'discrete infinity' by embedding phrases within phrases of the same type in a hierarchical structure. Without recursion, language does not have 'discrete infinity' and cannot embed sentences into infinity (with a '

Russian nesting dollA matryoshka doll is a Russian nesting doll which is a set of wooden dolls of decreasing size placed one inside the other. The first Russian nested doll set was carved in 1890 by Vasily Zvyozdochkin from a design by Sergey Malyutin, who was a folk crafts painter at Abramtsevo...

' effect). Everett contests that language must have discrete infinity, and asserts that the Pirahã language - which he claims lacks recursion - is in fact finite. He likens it to the finite game of

chessChess is a two-player board game played on a chessboard, a square-checkered board with 64 squares arranged in an eight-by-eight grid. It is one of the world's most popular games, played by millions of people worldwide at home, in clubs, online, by correspondence, and in tournaments.Each player...

, which has a finite number of moves but is nevertheless very productive, with novel moves being discovered throughout history.

### Recursion in plain English

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 that are to be taken based on a set of rules. The running of a procedure involves actually following the rules and performing the steps. An analogy might be that a procedure is like a cookbook in that it is the possible steps, while running a procedure is actually preparing the meal.

Recursion is related to, but not the same as, a reference within the specification of a procedure to the execution of some other procedure. For instance, a recipe might refer to cooking vegetables, which is another procedure that in turn requires heating water, and so forth. However, a recursive procedure is special in that (at least) one of its steps calls for a new instance of the very same procedure, like a

sourdoughSourdough is a dough containing a Lactobacillus culture, usually in symbiotic combination with yeasts. It is one of two principal means of biological leavening in bread baking, along with the use of cultivated forms of yeast . It is of particular importance in baking rye-based breads, where yeast...

recipe calling for some dough left over from the last time the same recipe was made. This of course immediately creates the danger 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, like a sourdough recipe that also tells you how to get some starter dough in case you've never made it before. Even if 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 of how far various simultaneous instances of the procedures have progressed. For this reason recursive definitions are very rare in everyday situations. An example could be the following procedure to find a way through a

mazeA maze is a tour puzzle in the form of a complex branching passage through which the solver must find a route. In everyday speech, both maze and labyrinth denote a complex and confusing series of pathways, but technically the maze is distinguished from the labyrinth, as the labyrinth has a single...

. Proceed forward until reaching either an exit or a branching point (a dead end is considered a branching point with 0 branches). If the point reached is an exit, terminate. Otherwise try each branch in turn, using the procedure recursively; if every trial fails by reaching only dead ends, return on the path that led to this branching point and report failure. Whether this actually defines a terminating procedure depends on the nature of the maze: it must not allow loops. In any case, executing the procedure requires carefully recording all currently explored branching points, and which of their branches have already been exhaustively tried.

### Recursive humor

Recursion is sometimes used humorously in computer science, programming or mathematics textbooks; the following two examples might be entries in a

glossaryA glossary, also known as an idioticon, vocabulary, or clavis, is an alphabetical list of terms in a particular domain of knowledge with the definitions for those terms...

:

**Recursion**
- See "Recursion".

**Recursion**
- If you still don't get it, see "Recursion".

A variation is found in the

indexIndex may refer to:-Business:* Index , a defunct UK catalogue retailer formerly owned by the Littlewoods group and known as Littlewoods Index* INDEX, a market research fair in Lucknow, India* Index fund, a collective investment scheme...

on page 269 of some editions of Kernighan and Ritchie's book "

The C Programming LanguageThe C Programming Language is a well-known programming book written by Brian Kernighan and Dennis Ritchie, the latter of whom originally designed and implemented the language, as well as co-designed the Unix operating system with which development of the language was closely intertwined...

"; thus the index entry recursively references itself:

- recursion 86, 139, 141, 182, 202,
**269**

The earliest version of this joke was in "Software Tools" by Kernighan and Plauger, and also appears in "The UNIX Programming Environment" by Kernighan and Pike. It did not appear in the first edition of The C Programming Language.

Another similar joke occurs in

GoogleGoogle Inc. is an American multinational public corporation invested in Internet search, cloud computing, and advertising technologies. Google hosts and develops a number of Internet-based services and products, and generates profit primarily from advertising through its AdWords program...

search engine: when a search for "recursion" is made, the site suggests "Did you mean: Recursion". (

Google Search for the word *recursion*)

Recursive acronymA recursive acronym is an acronym or initialism that refers to itself in the expression for which it stands...

s can also be examples of recursive humor.

PHPPHP is a general-purpose server-side scripting language originally designed for web development to produce dynamic web pages. For this purpose, PHP code is embedded into the HTML source document and interpreted by a web server with a PHP processor module, which generates the web page document...

, for example, stands for "PHP Hypertext Preprocessor" and

WINEWine is a free software application that aims to allow computer programs written for Microsoft Windows to run on Unix-like operating systems. Wine also provides a software library, known as Winelib, against which developers can compile Windows applications to help port them to Unix-like...

, for example, stands for "Wine Is Not an Emulator."

## Recursion in mathematics

#### Example: the natural numbers

The canonical example of a recursively defined set is given by the natural numbers:

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

#### Example: The set of true reachable propositions

Another interesting example is the set of all "true reachable" propositions in an

axiomatic systemIn mathematics, an axiomatic system is any set of axioms from which some or all axioms can be used in conjunction to logically derive theorems. A mathematical theory consists of an axiomatic system and all its derived theorems...

.

- if a proposition is an axiom, it is a true reachable proposition.
- if a proposition can be obtained from true reachable propositions by means of inference rules, it is a true reachable proposition.
- The set of true reachable propositions is the smallest set of propositions satisfying these conditions.

This set is called 'true reachable propositions' because in non-constructive approaches to the foundations of mathematics, the set of true propositions may be larger than the set recursively constructed from the axioms and rules of inference. See also

Gödel's incompleteness theoremsGödel's incompleteness theorems are two theorems of mathematical logic that establish inherent limitations of all but the most trivial axiomatic systems capable of doing arithmetic. The theorems, proven by Kurt Gödel in 1931, are important both in mathematical logic and in the philosophy of...

.

### Functional recursion

A

functionIn mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...

may be partly defined in terms of itself. A familiar example is the

Fibonacci numberIn mathematics, the Fibonacci numbers are the numbers in the following integer sequence:0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\; \ldots\; ....

sequence:

*F*(

*n*) =

*F*(

*n* − 1) +

*F*(

*n* − 2). For such a definition to be useful, it must lead to values which are non-recursively defined, in this case

*F*(0) = 0 and

*F*(1) = 1.

A famous recursive function is the

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

which, unlike the Fibonacci sequence, cannot easily 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 inductionStructural induction is a proof method that is used in mathematical logic , computer science, graph theory, and some other mathematical fields. It is a generalization of mathematical induction...

, a powerful generalization of

mathematical inductionMathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers...

which is widely used to derive proofs in

mathematical logicMathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...

and

computer scienceComputer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

.

### Recursive optimization

Dynamic programmingIn mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems which are only slightly smaller and optimal substructure...

is an approach to

optimizationIn mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....

which restates a multiperiod or multistep optimization problem in recursive form. The key result in dynamic programming is the

Bellman equationA Bellman equation , named after its discoverer, Richard Bellman, is a necessary condition for optimality associated with the mathematical optimization method known as dynamic programming...

,

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

## Recursion in computer science

A common method of simplification is to divide a problem into subproblems of the same type. As a

computer programmingComputer programming is the process of designing, writing, testing, debugging, and maintaining the source code of computer programs. This source code is written in one or more programming languages. The purpose of programming is to create a program that performs specific operations or exhibits a...

technique, this is called

divide and conquerIn computer science, divide and conquer is an important algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same type, until these become simple enough to be solved directly...

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 programmingIn mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems which are only slightly smaller and optimal substructure...

. 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

factorialIn mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n...

function, given here in C code: