Recursion

related topics
{math, number, function}
{food, make, wine}
{language, word, form}
{theory, work, human}
{god, call, give}
{film, series, show}
{woman, child, man}
{build, building, house}
{style, bgcolor, rowspan}

Recursion, in mathematics and computer science, is a method of defining functions in which the function being defined is applied within its own definition; specifically it is defining an infinite statement using finite components. The term is also used more generally to describe a process of repeating objects in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion.

Contents

Formal definitions of recursion

In mathematics and computer science, a class of objects or methods exhibit recursive behavior when they can be defined by two properties:

For example, the following is a recursive definition of a person's ancestors:

  • One's parents are one's ancestors (base case).
  • The parents of one's ancestors are also one's ancestors (recursion step).

The Fibonacci sequence is a classic example of recursion:

  • Fib(0) is 0 [base case]
  • Fib(1) is 1 [base case]
  • For all integers n > 1: Fib(n) is (Fib(n-1) + Fib(n-2)) [recursive definition]

A convenient mental model of recursion defines the recursive object (whether that object is an equation, an algorithm, an image, or a rule) in terms of "previously defined" objects of the same class. For example: How do you move a stack of 100 boxes? Answer: you move one box, remember where you put it, and then solve the smaller problem: how do you move a stack of 99 boxes? Eventually, you're left with the problem of how to move a single box, which you know how to do.

Full article ▸

related documents
Cantor set
Word problem for groups
Finite field
Inverse function
Inner product space
Naive set theory
Limit superior and limit inferior
Peano axioms
Addition
Matrix multiplication
Zermelo–Fraenkel set theory
Computational complexity theory
Markov chain
Topological space
Collatz conjecture
Pythagorean theorem
Mathematical induction
Wavelet
Bra-ket notation
Groupoid
Cauchy sequence
Forcing (mathematics)
Hash table
Recurrence relation
Johnston diagram
Pi
Non-standard analysis
Principal components analysis
XML
List of trigonometric identities