Recursion

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 | edit 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 well-known 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[change | edit 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.