Recursion

# Recursion

Overview

Recursion is the process of repeating items in a self-similar
Self-similarity
In 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 linguistics
Linguistics
Linguistics 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 logic
Logic
In 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 mathematics
Mathematics
Mathematics 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 science
Computer science
Computer 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 functions
Function (mathematics)
In 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.
Discussion

Encyclopedia

Recursion is the process of repeating items in a self-similar
Self-similarity
In 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 linguistics
Linguistics
Linguistics 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 logic
Logic
In 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 mathematics
Mathematics
Mathematics 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 science
Computer science
Computer 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 functions
Function (mathematics)
In 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 mathematics
Mathematics
Mathematics 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 science
Computer science
Computer 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:
1. A simple base case (or cases), and
2. 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
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 ancestor
Ancestor
An 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 number
Natural number
In 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 theory
Set theory
Set 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 Plotkin
Andrew Plotkin
Andrew 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 function
Function (mathematics)
In 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 fractal
Fractal
A 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 Chomsky
Noam Chomsky
Avram 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 English
English language
English 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 linguist
Linguistics
Linguistics 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 Everett
Daniel Everett
Daniel 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ã language
Pirahã language
Pirahã 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 doll
Matryoshka doll
A 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 chess
Chess
Chess 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 sourdough
Sourdough
Sourdough 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 maze
Maze
A 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 glossary
Glossary
A 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 index
Index
Index 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 Language
The C Programming Language (book)
The 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 Google
Google 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 acronym
Recursive acronym
A 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. PHP
PHP
PHP 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 WINE
Wine (software)
Wine 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 system
Axiomatic system
In 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 theorems
Gödel's incompleteness theorems
Gö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 function
Function (mathematics)
In 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 number
Fibonacci number
In 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 function
Ackermann function
In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total computable function that is not primitive recursive...

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 induction
Structural induction
Structural 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 induction
Mathematical induction
Mathematical 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 logic
Mathematical logic
Mathematical 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 science
Computer science
Computer 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 programming
Dynamic programming
In 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 optimization
Optimization (mathematics)
In 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 equation
Bellman equation
A 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 programming
Computer programming
Computer 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 conquer
Divide and conquer algorithm
In 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 programming
Dynamic programming
In 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 factorial
Factorial
In 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:

unsigned int factorial(unsigned int n)
{
if (n <= 1)
return 1;
else
return n * factorial(n-1);
}

The function calls itself recursively on a smaller version of the input (n - 1) and multiplies the result of the recursive call by n, until reaching the base case, analogously to the mathematical definition of factorial.

Recursion in computer programming is exemplified when a function is defined in terms of simpler, often smaller versions of itself. The solution to the problem is then devised by combining the solutions obtained from the simpler versions of the problem. One example application of recursion is in parsers 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
Recurrence relation
In mathematics, a recurrence relation is an equation that recursively defines a sequence, once one or more initial terms are given: each further term of the sequence is defined as a function of the preceding terms....

s are equations to define one or more sequences recursively. Some specific kinds of recurrence relation can be "solved" to obtain a non-recursive definition.

Use of recursion in an algorithm has both advantages and disadvantages. The main advantage is usually simplicity. The main disadvantage is often that the algorithm may require large amounts of memory if the depth of the recursion is very large.

## The recursion theorem

In set theory
Set theory
Set 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...

, this is a theorem guaranteeing that recursively defined functions exist. Given a set X, an element a of X 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 n.

### Proof of uniqueness

Take two functions and such that:

where a is an element of X.

It can be proved by mathematical induction
Mathematical induction
Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers...

that for all natural numbers n:
Base Case: so the equality holds for .

Inductive Step: Suppose for some . Then
Hence F(k) = G(k) implies F(k+1) = G(k+1).

By Induction, for all .

### Examples

Some common recurrence relations are:

• Golden Ratio
Golden ratio
In mathematics and the arts, two quantities are in the golden ratio if the ratio of the sum of the quantities to the larger quantity is equal to the ratio of the larger quantity to the smaller one. The golden ratio is an irrational mathematical constant, approximately 1.61803398874989...

: φ = 1 + (1/φ)... remembering that φ = 1 + (1/φ) then ... φ = 1 + (1/(1+(1/1+1/...)
• Factorial
Factorial
In 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...

:
• Fibonacci numbers:
• Catalan number
Catalan number
In combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involvingrecursively defined objects...

s: ,
• Computing compound interest
Interest
Interest is a fee paid by a borrower of assets to the owner as a form of compensation for the use of the assets. It is most commonly the price paid for the use of borrowed money, or money earned by deposited funds....

• The Tower of Hanoi
Tower of Hanoi
The Tower of Hanoi or Towers of Hanoi, also called the Tower of Brahma or Towers of Brahma, is a mathematical game or puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod...

• Ackermann function
Ackermann function
In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total computable function that is not primitive recursive...