recursive function

views updated

recursive function
1. In mathematics, a function whose usual or natural definition is in terms of itself.

2. In a program, a function procedure that calls itself.

3. (general recursive function, total recursive function) In the study of effective computability, a partial recursive function that happens to be total. For some authors, however, the terms recursive and general recursive are synonymous with partial recursive. It is useful here to summarize the various terms used in this area:

The term partial recursive function is often used in a general sense to mean any computable function on the natural numbers defined by a model of computation. However, strictly speaking, a partial recursive function is simply a function defined by primitive recursion and Kleene's μ-recursion scheme (see minimization). Not all such functions are total functions since the use of the μ-operator allows the possibility of nontermination.

A primitive recursive function, however, cannot involve the μ-operator and is hence guaranteed to be total. The Ackermann function is the standard example of a total recursive function that is not primitive recursive.