In programming recursion - a function call (procedure) from the same directly (simple recursion) or other functions (complex recursion), for example, function A calls function B, a function of B - the function of A. The number of nested function calls or procedure is called the depth of recursion.
Power recursive definition of the object that is able to describe the final determination of an infinitely large number of objects. With the help of a recursive program is also possible to describe an infinite computation, and without obvious repetition of the program.
Implementation of recursive calls of functions in the practice of programming languages and environments, usually based on the mechanism of the stack calls - the return address of local variables and functions are stored in the stack, so the next recursive call, this function uses its set of local variables and for the account is working correctly . The flip side of this is quite simple in structure mechanism is that the recursive calls are not free - for each recursive call requires a certain amount of RAM on your computer, and if too deep recursion may come a stack overflow calls. As a result, the usually recommended to avoid recursive programs, which lead (or, in some circumstances can lead) to a very deep recursion.
However, there is a special type of recursion, called the tail recursion. Interpreters and compilers of functional programming languages that support the optimization of the code (source and / or executable), automatically convert tail recursion to iteration, which provides execution of algorithms with tail recursion in a limited amount of memory. Such recursive computation, even if they are formally infinite (for example, when using recursion organized work commands, the host team of the user) will never lead to memory exhaustion. Unfortunately, not always standard programming languages clearly define how the terms should satisfy the recursive function that is guaranteed translator converted it into iteration. One of the rare exceptions - the language Scheme (a dialect of language Lisp), a description which contains all the necessary information. See also the examples of realization of function factorial.
A description of the type of data can contain a reference to itself. Such structures are used when describing the lists and graphs. Example description of the list (C + +):
class element_of_list
(
element_of_list * next; / * link to next element of the same type * /
int data; / * some data * /
);
Recursive data structure often makes use of recursion for processing these data.