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.

Notation

In mathematics

Recursive functions are notated similarly to piecewise functions. An example of a piecewise function is the absolute value function:

$\operatorname{abs}(x) = \begin{cases} x & \text{if }x \geq 0 \\ -x & \text{if }x < 0 \end{cases}$

To evaluate this function, we find the first line within the curly braces for which the condition on the right hand side is satisfied, and use the expression on the left hand side as the value. Thus, if $x \geq 0$, then the value of $\operatorname{abs}(x)$ is $x$, whereas if $x < 0$, then the value of $\operatorname{abs}(x)$ is instead $-x$.

Often, the condition on the last line will be replaced with the word "otherwise". This is like the else condition in a case statement (switch in C and related languages); it is chosen when none of the preceding conditions are satisfied. Thus we could rewrite the above as

$\operatorname{abs}(x) = \begin{cases} x & \text{if }x \geq 0 \\ -x & \text{otherwise} \end{cases}$

It is good form, but not strictly necessary, to make the conditions in the definition exhaustive and mutually exclusive, that is, exactly one condition should be true for each element in the domain. If they are not exhaustive, it is a sign that the domain was poorly specified, whereas if they are not mutually exclusive then it can be slightly confusing.

A recursive function is characterized by the recurrence of the function name in one or more of the left-hand expressions within the brace. Here is a classic example:

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

The domain of the function $F$ is $\mathbb{N}_1$. We see that $F(1) = 1$ and $F(2) = 1$. To evaluate $F(3)$, we must use the "otherwise" clause, and hence we see that

$F(3) = F(3-1) + F(3-2) = F(2) + F(1) = 1 + 1 = 2$

$F(4) = F(4-1) + F(4-2) = F(3) + F(2) = 2 + 1 = 3$

$F(5) = F(5-1) + F(5-2) = F(4) + F(3) = 3 + 2 = 5$

(and so on)

The cases in the definition that call the defined function are called recursive cases; the "otherwise" line in the definition of $F$ is the recursive case. Those that do not are called base cases; the line that defines $F(1) = F(2) = 1$ is the base case. Every recursive function has at least one recursive case (if it did not, it would not be called recursive) and at least one base case. This is because a recursive function definition without a base case would be an endlessly circular definition; attempting to evaluate the function would lead to endless or infinite recursion.

In code

Nearly all mainstream programming languages that support functions support recursive functions. (A language such as HTML is an obvious exception; it is intended to describe a document instead of a computation, and hence lacks functions altogether). In these languages, in any place in the code where a function calls another function, it can just as well call itself using the same notation. The code parallels the mathematical notation, for example:

C:

int F(int x)
{
    if (x == 1 || x == 2)
        return 1;
    else // i.e., "otherwise"
        return F(x - 1) + F(x - 2);
}

Haskell:

f :: Int -> Int
f x | x == 1 || x == 2   =   1
    | otherwise          =   f (x-1) + f (x-2)

(Note that function names are not allowed to start with uppercase letters in Haskell.)