# 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 ${\displaystyle n!=n(n-1)!,n>0}$ and ${\displaystyle 0!=1}$ by definition. In this case the domain is split into ${\displaystyle \{1,2,3,...\}}$ and ${\displaystyle \{0\}}$.

• If ${\displaystyle n>0}$ then return ${\displaystyle n\times f(n-1)}$.
• If ${\displaystyle n=0}$ then return ${\displaystyle 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.