Concept

Recursive definition

Overview

In mathematics and computer science, a recursive definition, or inductive definition, is used to define the elements in a set in terms of other elements in the set (Aczel 1977:740ff). Some examples of recursively definable objects include factorials, natural numbers, Fibonacci numbers, and the Cantor ternary set.

A recursive definition of a function defines values of the function for some inputs in terms of the values of the same function for other (usually smaller) inputs. For example, the factorial function n! is defined by the rules

(

)

(

)

⋅

{\displaystyle {\begin{aligned}&0!=1.\\&(n+1)!=(n+1)\cdot n!.\end{aligned}}}

This definition is valid for each natural number n, because the recursion eventually reaches the base case of 0. The definition may also be thought of as giving a procedure for computing the value of the function n!, starting from n = 0 and proceeding onwards with n = 1, 2, 3 etc.

The recursion theorem states that such a definition indeed defines a function that is unique. The proof uses mathematical induction.

An inductive definition of a set describes the elements in a set in terms of other elements in the set. For example, one definition of the set ⁠

{\displaystyle \mathbb {N} }

⁠ of natural numbers is:

0 is in ⁠

{\displaystyle \mathbb {N} .}

⁠

If an element n is in ⁠

{\displaystyle \mathbb {N} }

⁠ then n + 1 is in ⁠

{\displaystyle \mathbb {N} .}

⁠

{\displaystyle \mathbb {N} }

⁠ is the smallest set satisfying (1) and (2).

There are many sets that satisfy (1) and (2) – for example, the set {0, 1, 1.649, 2, 2.649, 3, 3.649, …} satisfies the definition. However, condition (3) specifies the set of natural numbers by removing the sets with extraneous members.

Properties of recursively defined functions and sets can often be proved by an induction principle that follows the recursive definition. For example, the definition of the natural numbers presented here directly implies the principle of mathematical induction for natural numbers: if a property holds of the natural number 0 (or 1), and the property holds of n + 1 whenever it holds of n, then the property holds of all natural numbers (Aczel 1977:742).

Overview adapted from Wikipedia (CC BY-SA 4.0; see the article history for authors).

Possible passages

Found by search and not yet checked by a person; they may only mention the idea in passing.

Any such select set is called the set of postulates, or premises, from which the reasoning proceeds. The reasoning is nothing else than the exhibition of the whole pattern of general conditions involved in the pattern derived from the selected postulates.
Alfred North Whitehead, Science and the modern world
States what Recursive definition is.
Read the chapter · Open in the reader
Thus there arises a classification of modes of formation, or in the language commonly used by mathematicians, a classification of Functions. Any number, considered as formed from any other number, is called a function of it; and there are as many kinds of functions as there are modes of formation. The simple functions are by no means numerous, most functions being formed by the combination of several of the…
John Stuart Mill, A System of Logic, Ratiocinative and Inductive
States what Recursive definition is.
Read the chapter · Open in the reader
It must be granted that Cantor’s definition includes every series that is continuous; nor can it be objected that it includes any important or indubitable case of a series not continuous. Nevertheless, it has some serious defects. In the first place, it turns upon metrical considerations; while the distinction between a continuous and a discontinuous series is manifestly non-metrical. In the next place, a perfect…
Charles S. Peirce, Chance, Love, and Logic
States what Recursive definition is.
Read the chapter · Open in the reader

Related ideas

Place in the tradition

Part of Linear logic.

Explore Recursive definition in the interactive graph →