| |
Recursion (Latin, ‘running back over’), in mathematics, is a method of constructing functions from ones which already exist, and is related to the idea of induction. It is the way in which many important functions are defined, including addition and multiplication in Peano arithmetic. Suppose that f is a function from some set X to itself, and that a is a member of X. Then there is a function g from the natural numbers to X defined by g(0) = a, and for each number n, g(n + 1) = f(g(n)). (Addition is defined using the successor function, the function of counting, as f, and multiplication is defined using addition as f.)
Recursion is also used in computability, where it is used to define the set of recursively enumerable functions, which turn out to be those which computers can calculate. SMcL |
|
