Recursion facts for kids

Kids Encyclopedia Facts
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.


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.

Images for kids

Recursion Facts for Kids. Kiddle Encyclopedia.