Recursive function

Recursion is the property exhibited by entities that are defined in terms of themselves, that is, recur in themselves. In computer science, the most important recursive entities are recursively defined functions. Mathematical functions are usually thought of as sets of ordered pairs, the first element in the pair from the domain, the second from the range, and, hence, a function cannot be intrinsically recursive. However, functions in computer programs are instead defined in a form that allows computers to evaluate them (efficiently, it is hoped), and the definition of a function in a computer program may reference the function itself. Such a function, that occurs in its own definition, is said to be recursively defined, and, with the understanding that we are speaking of the definition of a function rather than its abstract mathematical essence, we will refer to them simply as recursive functions. The term recursion is then defined also as the process of evaluating recursive functions, and, by extension, the formulation of algorithms in terms of recursive functions.

Example

Let $F(n)$ denote the $n$^th Fibonacci number, where $n$ is a natural number and $F(1) = F(2) = 1$. We may define $F$ as a function, as follows:

$F(x) = \begin{cases} 1 & \text{if }x = 1\text{ or }x = 2 \\ F(x-1) + F(x-2) & \text{otherwise} \end{cases}$