Recursion

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

Recursion is a word from mathematics and computer science. It is used to define a thing, such as a function or a set. A recursive definition uses the thing it is defining as part of the definition.

Description

Usually, a recursive function refers to itself in some cases (or inputs), but not in every case. A function that referred to itself in every case would never terminate.

When a function refers to itself, it often uses a smaller input than the input it was given. In this way, it can solve a problem by first solving a simpler version of the problem.

Example

An example of a recursive function [math]\displaystyle{ f(n) }[/math] is:

• If [math]\displaystyle{ n \gt 0 }[/math] then return [math]\displaystyle{ n \times f(n-1) }[/math].
• If [math]\displaystyle{ n = 0 }[/math] then return [math]\displaystyle{ 1 }[/math].

This function computes the factorial of a natural number. It works because [math]\displaystyle{ n!=n(n-1)!, n \gt 0 }[/math] and [math]\displaystyle{ 0!=1 }[/math].

The definition has two cases: a recursive case for [math]\displaystyle{ n\gt 0 }[/math], and a case for [math]\displaystyle{ n=0 }[/math] that is not recursive. The case that is not recursive is called a "base case".

Uses

Recursion can be used to write computer programs. A program that uses recursion may be easier to write and understand than a program that does the same thing without recursion.

Recursion is used in mathematics to prove theorems. This method is called induction.

The idea of recursion can be seen in art and language. For example:

• A fractal image contains smaller versions of itself.
• In the rules of grammar, a sentence can be part of another sentence.

Easter Eggs

In the Google search engine, if you type up "recursion", it will say "Did you mean: Recursion", a reference to the meaning of recursion.

RecursionRecursively Enumerable Sets Media

• 

  A visual form of recursion known as the Droste effect. The woman in this image holds an object that contains a smaller image of her holding an identical object, which in turn contains a smaller image of herself holding an identical object, and so forth. 1904 Droste cocoa tin, designed by Jan Misset

• 

  Ouroboros, an ancient symbol depicting a serpent or dragon eating its own tail

• 

  Sourdough starter being stirred into flour to produce sourdough: the recipe calls for some sourdough left over from the last time the same recipe was made.

• 

  A plaque commemorates the Toronto Recursive History Project of Toronto's Recursive History.

• 

  The Sierpinski triangle—a confined recursion of triangles that form a fractal

• 

  Recursive dolls: the original set of Matryoshka dolls by Zvyozdochkin and Malyutin, 1892

• 

  Front face of Giotto's Stefaneschi Triptych, 1320, recursively contains an image of itself (held up by the kneeling figure in the central panel).