Recursive definition

Recursive definition

A recursive definition or inductive definition is one that defines something in terms of itself (that is, recursively), albeit in a useful way. For it to work, the definition in any given case must be well-founded, avoiding an infinite regress.

In simple terms, the recursive definition is one that grows an awareness and clarity upon itself toward a conclusive end, with each recurrence contributing something new toward the end definition. The recurring theme or influence will strengthen the definition as it is repeatedly applied to itself, and will eventually arrive at a point where no more recurrence is required.

Frequently found in mathematics, and computer languages, the recursive definition is a created process by which eventual results are found only by the developing impact of the recurrence. A simple example would be: X+1=Y where X=1+Y until Y equals 10. So, then 1+1=2, 2+1=3, 3+1=4, and so on until 9+1=10, which then completes the recurrence of the process and the result is 10.

In engineering it is possible to create a progressive equation toward an understood conclusion where the result is known and the available resources and steps toward it are known, but the total accumulation of steps and resources to be used is not known. An example would be the propelling force needed to take a rocket from lift-off to orbit. With each ounce of fuel consumed the force needed to propel the rocket is reduced because the rocket weighs less. As the rocket escapes Earth's gravitational pull, the amount of fuel required is reduced even more, but at a different rate than the impact of the fuel weight lost. A recursive equation would seek to define the total fuel required to achieve orbit by repeatedly calculating the elements involved according to predictable changes as related to time, gravity, energy, force, mass, and practical aspects such as size, weather, and safety. The eventual answer is subject to all of the recurring influences along the path of the rocket's trajectory.

Most recursive definition have three foundations: a basis, an inductive clause, and an extremal clause.

The difference between a circular definition and a recursive definition is that a recursive definition must have "base cases", cases that satisfy the definition "without" being defined in terms of the definition itself, and all other cases comprising the definition must be "smaller" ("closer" to those base cases that terminate the recursion).

In contrast, a circular definition has no base cases and defines itself only in terms of itself, rather than a version of itself closer to a base case. This leads to a vicious circle. Thus, the quip of "Recursive definition: see "Recursive definition" is inaccurate: this is a circular definition because it has no end to the recurrence.

Examples of recursive definitions

Prime numbers

The prime numbers can be defined as consisting of:
* 2, the smallest prime;
* each positive integer which is not evenly divisible by any of the primes smaller than itself.The integer 2 is our base case; checking the primality of any larger integer "X" requires us to know the primality of every integer between X and 2, but each such integer is closer to our base case of 2 than X is.

Non-negative even numbers

The even numbers can be defined as consisting of
* 0 is in the set N of non-negative evens (basis clause)
* For any element x in the set N, x+2 is in N (inductive clause)
* Nothing is in N unless it is obtained from the basis and inductive clauses (extremal clause)

Well formed Formula

It is chiefly in logic or computer programming that recursive definitions are found. For example, a well formed formula (wff) can be defined as:
#a symbol which stands for a proposition - like p means "Connor is a lawyer."
#The negation symbol, followed by a wff - like Np means "It is not true that Connor is a lawyer."
#Any of the four binary connectives (C, A, K, or E) followed by two wffs. The symbol K means "both are true", so Kpq may mean "Connor is a lawyer and Mary likes music."

The value of such a recursive definition is that it can be used to determine whether any particular string of symbols is "well formed".

* Kpq is well formed, because it's K followed by the atomic wffs p and q.
* NKpq is well formed, because it's N followed by Kpq, which is in turn a wff.
* KNpNq is K followed by Np and Nq; and Np is a wff, etc.

Recursive definitions in hacker culture

The computer language LISP has a similar definition, and some fans of LISP have playfully constructed acronyms which are recursive but with an infinite regress. Hackers seem to find this a source of immense amusement. For example,

* GNU means "GNU's Not Unix".
* WINE means "WINE Is Not an Emulator"

Recursive definitions in common parlance and philosophical terminology

In common parlance and philosophical terminology, definitions often contain recursive elements.

*"Nothing" is defined by properties it does not have. "There's nothing in that room." describes that there is nothing notable in the room, most probably there is air in the room, but the air would be irrelevant as it does not correspond to the necessary properties that would have been defined or implied in the preceding sentence. The phrases "the nothing(ness)" and "absolute nothing(ness)" would describe something that lacks any property, something to which nothing can be described to, indeed something that does not exist, not in this universe, not in one's imagination, nowhere.
*"Science" may be seen as the practice of describing the empirical or observable facts of nature (or at least trying to do so). As scientists only consider nature for as far as it can be observed, they tend to see non-observable things as supernatural and/or not existing in this universe. Supernatural or paranormal phenomena, if they exist, would only be described as thus because they go beyond how nature is commonly perceived.


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • recursive definition — noun (mathematics) a definition of a function from which values of the function can be calculated in a finite number of steps • Topics: ↑mathematics, ↑math, ↑maths • Hypernyms: ↑definition * * * rə̇ˈkər]s]iv, rē , (ˈ)rē]|k , kə̄], kəi], ]z], ]ēv …   Useful english dictionary

  • recursive definition — noun A definition of a term within which the term itself appears, and that is well founded, avoiding an infinite regress. Syn: inductive definition See Also: circular definition …   Wiktionary

  • recursive definition — Logic. a definition consisting of a set of rules such that by repeated application of the rules the meaning of the definiendum is uniquely determined in terms of ideas that are already familiar. [1935 40] * * * …   Universalium

  • Recursive least squares filter — Recursive least squares (RLS) algorithm is used in adaptive filters to find the filter coefficients that relate to recursively producing the least squares (minimum of the sum of the absolute squared) of the error signal (difference between the… …   Wikipedia

  • Definition — For other uses, see Definition (disambiguation). A definition is a passage that explains the meaning of a term (a word, phrase or other set of symbols), or a type of thing. The term to be defined is the definiendum. A term may have many different …   Wikipedia

  • recursive — A procedure that is applied once, and then applied to the result of that application, and so on. A recursive definition (definition by induction) defines the result of some operation for 0, and then the result for any number n + 1 in terms of the …   Philosophy dictionary

  • definition — I (Roget s IV) n. 1. [Expressed meaning of a term] Syn. meaning, explanation, description, signification, denotation, diagnosis, analogue, synonym, exposition, elucidation, rendering, drift, sense, referent, interpretation, formalization,… …   English dictionary for students

  • Recursive categorical syntax — Recursive categorical syntax, also sometimes called algebraic syntax, is an algebraic theory of syntax developed by Michael Brame as an alternative to transformational generative grammar. It is a type of dependency grammar, and is related to link …   Wikipedia

  • Recursive languages and sets — This article is a temporary experiment to see whether it is feasible and desirable to merge the articles Recursive set, Recursive language, Decidable language, Decidable problem and Undecidable problem. Input on how best to do this is very much… …   Wikipedia

  • Recursive set — In computability theory, a set of natural numbers is called recursive, computable or decidable if there is an algorithm which terminates after a finite amount of time and correctly decides whether or not a given number belongs to the set. A more… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”