Recursive function

(mathematics) Functions that can be obtained by a finite number of operations, computations, or algorithms.

A function that maps natural numbers to natural numbers and is special in that it must be calculable by using a precisely specified algorithm. The mathematical definitions of partial recursive functions and recursive functions were developed to give a precise mathematical characterization of those functions or operations on the natural numbers which are computable by using effective procedures.

An effective procedure is a procedure or process determined by a finite list of precise instructions. There is no upper bound on the number of instructions in this list. These instructions can be carried out in a discrete one-step-at-a-time fashion. The only equipment needed is pencil and paper, and an unlimited supply is assumed to be available. No creativity is involved in applying these instructions, and no random devices such as flipping a coin are allowed in carrying them out.

An effective procedure may be used to calculate a function as follows: The calculator inputs to the effective procedure a natural number (0, 1, 2, 3, …) and allows the procedure to be carried out on this input. If an ouput is obtained, the function is said to be defined at this input and its value at this input is the output so obtained. Any function which can be computed in this way is called effectively computable. For example, addition and multiplication of natural numbers are effectively computable functions.

The notion of effective procedure is intuitive and vague. In the setting of an idealized computing device called a Turing machine, a more precise definition of certain effectively computable functions can be given. See also Automata theory; Gödel's theorem; Logic.

Recursive function may refer to:

• Recursion (computer science): a procedure or subroutine, implemented in a programming language, whose implementation references itself
• μ-recursive function, defined from a particular formal model of computable functions using primitive recursion and the μ operator
• Computable function, or total recursive function, a function computable by a Turing machine

See also

• Recursive

This disambiguation page lists articles associated with the same title. If an internal link led you here, you may wish to change the link to point directly to the intended article.

This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)