Definition Mathematically, the definition of recursive function is as follows: for a certain function f(x), its domain is set A, then if a certain value X0 in set A, its function value f(x0) is determined by f(f(x0)), then f(x) is called recursive function.

In programming languages, functions that directly or indirectly call themselves are called recursive functions. The construction of a function usually requires a function or a process to complete.

In mathematical logic and computer science, recursive function or μ-recursive function is a function from natural number to natural number, which is "computable" in an intuitive sense. In fact, in the computability theory, it is proved that the recursive function is the computable function of Turing machine. Recursive function is related to primitive recursive function, and its inductive definition (see below) is based on primitive recursive function. However, not all recursive functions are primitive recursive functions-the most famous one is Ackerman function.

Other equivalent function classes are λ-recursive function and Markov algorithm computable function.