# Recursion

A visual form of recursion is the Droste effect. It leads to self-similar images.

Recursion is a word from mathematics. In mathematics and in computer science, it is used to define a thing, usually a function. Unlike with normal definitions, the function to be defined can be used to define itself.

## Description

A recursive function usually has different definitions for different parts of its domain. One or more of these definitions includes a reference to itself. Although functions that only have recursive definitions can be very usefull for theoretical purposes, they never terminate. Recursive functions that terminate include at least one non-recursive definition.

A popular example of a recursive function is the function that evaluates to the factorial of some natural number. It exploits the fact that $n!=n(n-1)!, n > 0$ and $0!=1$ by definition. In this case the domain is split into $\{1,2,3,...\}$ and $\{0\}$.

• If $n > 0$ then return $n \times f(n-1)$.
• If $n = 0$ then return $1$.

## Recursively enumerable sets

Sometimes it is impossible to say if a recursion will terminate. This can happen for recursively enumerable sets. An algorithm that examimes if an element belongs to such a set will always terminate if the answer is yes but it may not terminate if the answer is no.