Preferred term: recursion

<mathematics, computer programming> When a function (or procedure) calls itself. Such a function is called "recursive". If the call is via one or more other functions then this group of functions are called "mutually recursive".

If a function will always call itself, however it is called, then it will never terminate. Usually however, it first performs some test on its arguments to check for a "base case" - a condition under which it can return a value without calling itself.

The canonical example of a recursive function is factorial:

factorial 0 = 1 factorial n = n * factorial (n-1)

Functional programming languages rely heavily on recursion, using it where a procedural language would use iteration.

See also: recursion, recursive definition, tail recursion.

(01 Feb 1996)

The act of recurring; return. (Math) The calculation of a mathematical expression (or a quantity) by repeating an operation on another expression which was derived by application of the same operation, on an expression which itself was the result of similar repeated applications of that same operation on prior results. The series of operations is terminated by specifying an initial or terminal condition. (Computers) A programming technique in which a function calls itself as a subfunction. Such calls may be repeated in series to arbitrary depth, provided that a terminating condition is given so that the final (deepest) call will return a value (rather than continue to recurse), which then permits the next higher call to return a value, and so forth, until the original call returns a value to the calling program.

Origin: L. Recursio. See Recur.

(01 Mar 1998)

recursion theorycomputing dictionary

<theory> The study of problems that, in principle, cannot be solved by either computers or humans.

[Proper definition?]

(01 Apr 1999)

Preferred term: recursion

recurse, recursion, recursion, recursion theory < Prev | Next > recursive acronym, recursive definition

Bookmark with: icon icon icon icon iconword visualiser Go and visit our forums Community Forums

recursive acronymcomputing dictionary

<convention> A hackish (and especially MIT) tradition is to choose acronyms and abbreviations that refer humorously to themselves or to other acronyms or abbreviations. The classic examples were two MIT editors called EINE ("EINE Is Not Emacs") and ZWEI ("ZWEI Was EINE Initially"). More recently, there is a Scheme compiler called LIAR (Liar Imitates Apply Recursively), and GNU stands for "GNU's Not Unix!" - and a company with the name CYGNUS, which expands to "Cygnus, Your GNU Support".

See also: mung.

(01 Mar 1995)

recursive definitioncomputing dictionary

See recursive definition.

(03 Feb 2009)

recursion theory, recursive, recursive acronym < Prev | Next > recursive descent parser

Bookmark with: icon icon icon icon iconword visualiser Go and visit our forums Community Forums

recursive descent parsercomputing dictionary

<grammar> A "top-down" parser built from a set of mutually-recursive procedures or a non-recursive equivalent where each such procedure usually implements one of the productions of the grammar. Thus the structure of the resulting program closely mirrors that of the grammar it recognises.

["Recursive Programming Techniques", W.H. Burge, 1975, ISBN 0-201-14450-6].

(01 Mar 1995)

Recursive Functional Algorithmic Languagecomputing dictionary

<programming language>

(REFAL) A language developed by V.F. Turchin (later at CUNY?) in Moscow in about 1972.

See also: supercompilation.

[V.F. Turchin, "An algorithm of generalisation in the supercompiler", Workshop on partial evaluation and mixed computations, Oct 1987, Denmark, Eds. D. Bjorner, A.P. Ershov, N.D. Jones].

[V. Turchin, "Supercompiler System Based on the Language Refal", V. Turchin, SIGPLAN Notices 14(2):46-54 (Feb 1979)].

(01 Apr 1998)

Recursive Macro Actuated Generatorcomputing dictionary

<tool> (RMAG) Robert A. Magnuson, NIH ca 1970.

A stand-alone macroprocessor for IBM 360/370 under VS or OS. Many built-in features and a library of several hundred macros. Several large systems were written in RMAG to generate source code for languages such as IBM JCL, IBM assembly language, COBOL.

There was also a system (SLANG: Structured LANGuage compiler) which would generate 370 assembly language from a pseudo-structured-programming language, based on Michael Kessler's structure programming macros developed at IBM.

["Project RMAG--RMAG22 User's Guide", R.A. Magnuson, NIH-DCRT-DMB-SSS-UG103, NIH, DHEW, Bethesda, MD 20205 (1977)].

Acronym: RMAG

(01 Mar 1995)

recursive typecomputing dictionary

A data type which contains itself. The commonest example is the list type, in Haskell:

data List a = Nil | Cons a (List a)

which says a list of a's is either an empty list or a cons cell containing an 'a' (the "head" of the list) and another list (the "tail").

Recursion is not allowed in Miranda or Haskell synonym types, so the following Haskell types are illegal:

type Bad = (Int, Bad) type Evil = Bool -> Evil

whereas the seeminly equivalent algebraic data types are acceptable:

data Good = Pair Int Good data Fine = Fun (Bool->Fine)

(03 Feb 2009)