Computability is often defined in terms of recursive functions, recursively enumerable sets, recursive sets. Is the reason behind this – the following:
- a function that can be computed is a recursive function – ie. parts of such function can be simplified and substituted, and then again simplified, substituted, and so forth
? Is this the meaning behind various recursive tools? Like: $\lambda$-calculus, Markov-algorithms, formal languages.
In computability theory a "recursive function" is simply a function that can be effectively computed - by $\lambda$ calculus, or by a Turing machine, or by a register machine, or other equivalent models of computability. Recursive functions are also called "computable functions".
There is more information on the Wikipedia article.
The term "recursive" itself is historical and is not directly related to the idea of "recursive functions" from introductory programming courses.