# Difference between revisions of "Recursion"

m (Fixed recursive link) |
m (Fixed link for real this time) |
||

Line 20: | Line 20: | ||

* [[Sequence]] | * [[Sequence]] | ||

* [[Induction]] | * [[Induction]] | ||

− | * [ | + | * [http://artofproblemsolving.com/wiki/index.php?title=Recursion Recursion] |

[[Category:Combinatorics]] | [[Category:Combinatorics]] | ||

[[Category:Definition]] | [[Category:Definition]] |

## Revision as of 20:31, 25 April 2016

**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 .

In computer science, recursion also refers to the technique of having a function repeatedly call itself. The concept is very similar to recursively defined mathematical functions, but can also be used to simplify the implementation of a variety of other computing tasks.

## Examples

- Mock AIME 2 2006-2007 Problem 8 (number theory)
- A combinatorical use of recursion: 2006 AIME I Problem 11
- Another combinatorical use of recursion: 2001 AIME I Problem 14
- Use of recursion to compute an explicit formula: 2006 AIME I Problem 13
- Use of recursion to count a type of number: 2007 AMC 12A Problem 25
- Yet another use in combinatorics 2008 AIME I Problem 11