# Catalogue of Artificial Intelligence Techniques

View Maths as: Images | MathML

## Recursion

Aliases: Recursive Function

Keywords: Turing machine

### Categories: Inference and Reasoning , Knowledge Representation , Theorem Proving

Author(s): Fausto Giunchiglia

Recursion theory has been developed by logicians (mainly K. Gödel and S.C. Kleene) in the 1930's as a way to formalise metamathematics. Recursive functions can be given by definitions involving reference to the function being defined. For instance:

if  $n=0$   then $1$ else $n*f\left(n-1\right)$

where $n$ is a natural number, is the recursive definition of the factorial. Since recursive functions are all and only the functions computable by idealised computers (Turing machines), recursion theory has been extended to domains different from the natural numbers (e.g., lists) and used by computer scientists as a powerful tool to reason about programs. Applications include the theory of computation, complexity of programs, program synthesis and program verification.

### References:

• Kleene, S., Introduction to Metamathematics , Van Nostrand, New York, 1952.