Recursion

Recursion is a method of defining something (usually a sequence or function) in terms of previously defined values. The most famous example of a recursive definition is that of the Fibonacci sequence. If we let be the th Fibonacci number, the sequence is defined recursively by the relations and . (That is, each term is the sum of the previous two terms.) Then we can easily calculate early values of the sequence in terms of previous values: , and so on.

Often, it is convenient to convert a recursive definition into a closed-form definition. For instance, the sequence defined recursively by and for also has the closed-form definition (where "!" represents the factorial function).

Examples

• Mock AIME 2 2006-2007 Problem 8 (number theory)
• A combinatorical use of recursion: 2006 AIME I Problem 11
• Use of recursion to compute an explicit formula: 2006 AIME I Problem 13

See also

• Combinatorics
• Sequence
• Induction