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.

Recursion consists of two steps:

  1. Are we done yet? If so, return the results. Without this step, a recursion would go on forever.
  2. If not, recurse: simplify the problem, solve the simpler problem(s), and assemble the results into a solution for the original problem. Then return that solution.

An example might be how to define ancestor, using recursion:

  1. A person's parents are his or her ancestors (base hypothesis).
  2. The ancestors of a person's ancestors are also ancestors of the person being considered (recursion step).