recursive

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 result for n; thus the operation becomes defined for all numbers (the notion may be extended to describe the same process on any well-ordered set). For example, if n' denotes the successor of n, then multiplication may be defined: a × 0 = 0; a × b' = (a × b) + a.
A function in mathematics is primitive recursive if it is definable by recursion and substitution from a number of basic functions. These are commonly the successor function, the zero function (the function whose value is zero for every argument), the projection functions (that extract the ith member of any ordered n-tuple), and constant functions (that return the same number as value for any arguments).
A function is general recursive (or recursive) if it can be defined by means of primitive recursive functions and the minimization or µ operator. This defines a resulting function, h, out of a given function f according to the schema: h(x 1… x n) = the least y for which f(x 1… x n, y ) = 0 and is undefined if there is no such y .
A set is recursively enumerable if there is a recursive function that enumerates its members, i.e. if they can be ordered as f(0), f (1), f (2)…where f is a general recursive function. If both a set and its complement can be ordered, then the set is general recursive, or recursive. The importance of the notion is that it corresponds with being decidable, or effectively computable. Suppose, for example, that the theorems of some system form a recursive set, then we can find whether a candidate formula is a theorem by enumerating both the theorems and the non-theorems; we can be sure that in a finite time the formula will turn up on one list or another, and this procedure decides the matter. According to Church's theorem the set of theorems of the predicate calculus cannot be represented as a recursive set, so by Church's thesis the calculus is undecidable.

Philosophy dictionary. . 2011.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Recursive — may refer to:*Recursion *Recursively enumerable language *Recursively enumerable set *Recursive filter *Recursive function *Recursive language *Recursive acronym *Recursive set *Primitive recursive function …   Wikipedia

  • recursive — [ri kʉr′siv] adj. 1. reapplying the same formula or algorithm to a number or result in order to generate the next number or result in a series 2. returning again and again to a point or points already made [a recursive style of writing] …   English World dictionary

  • recursive — 1790, from L. recurs , stem of recurrere (see RECUR (Cf. recur)) + IVE (Cf. ive). Mathematical sense is from 1934. Related: Recursively …   Etymology dictionary

  • récursive — ● récursif, récursive adjectif (anglais recursive, du latin recursum, de recurrere, revenir en arrière) Se dit d une règle ou d un élément doués de récursivité. Se dit d un programme informatique organisé de manière telle qu il puisse se rappeler …   Encyclopédie Universelle

  • recursive — adjective a) drawing upon itself, referring back. The recursive nature of stories which borrow from each other b) of an expression, each term of which is determined by applying a formula to preceding terms …   Wiktionary

  • recursive — adjective Date: 1934 1. of, relating to, or involving recursion < a recursive function in a computer program > 2. of, relating to, or constituting a procedure that can repeat itself indefinitely < a recursive rule in a grammar > • recursively… …   New Collegiate Dictionary

  • Récursive — Récursif Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom …   Wikipédia en Français

  • recursive — recursively, adv. recursiveness, n. /ri kerr siv/, adj. 1. pertaining to or using a rule or procedure that can be applied repeatedly. 2. Math., Computers. pertaining to or using the mathematical process of recursion: a recursive function; a… …   Universalium

  • recursive — algorithmic algorithmic adj. 1. of or pertaining to an algorithm. {recursive} [1913 Webster] 2. definitively solvable by a finite number of steps; said of mathematical or logical problems. Contrasted with {heuristic}. [WordNet 1.5] …   The Collaborative International Dictionary of English

  • Recursive partitioning — is a statistical method for multivariable analysis.cite book |author=Breiman, Leo |title=Classification and Regression Trees |publisher=Chapman Hall/CRC |location=Boca Raton |year=1984 |pages= |isbn=0 412 04841 8 |oclc= |doi=] . Recursive… …   Wikipedia

Share the article and excerpts

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