From Wikipedia, the free encyclopedia
Jump to: navigation, search
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[change | change source]

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 and by definition. In this case the domain is split into and .

  • If then return .
  • If then return .

Recursively enumerable sets[change | change source]

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.