
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 selfsimilar 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(n1) + Fib(n2)) [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 
Braket notation 
Groupoid 
Cauchy sequence 
Forcing (mathematics) 
Hash table 
Recurrence relation 
Johnston diagram 
Pi 
Nonstandard analysis 
Principal components analysis 
XML 
List of trigonometric identities 
