Difference between revisions of "Recursion"
m (→Examples: -- funny whoever did that - finally got noticed) |
Blippy1998 (talk | contribs) (changed URLs to avoid immediate viewing of the solution, also changed title of one URL) |
||
| Line 8: | Line 8: | ||
== Examples == | == Examples == | ||
| − | * [[Mock_AIME_2_2006- | + | * [[Mock_AIME_2_2006-2007_Problems#Problem_8 | Mock AIME 2 2006-2007 Problem 8]] ([[number theory]]) |
* A combinatorical use of recursion: [[2006_AIME_I_Problems#Problem_11|2006 AIME I Problem 11]] | * A combinatorical use of recursion: [[2006_AIME_I_Problems#Problem_11|2006 AIME I Problem 11]] | ||
| − | * Another combinatorical use of recursion: [[ | + | * Another combinatorical use of recursion: [[2001_AIME_I_Problems#Problem_14| 2001 AIME I Problem 14]] |
* Use of recursion to compute an explicit formula: [[2006_AIME_I_Problems#Problem_13| 2006 AIME I Problem 13]] | * Use of recursion to compute an explicit formula: [[2006_AIME_I_Problems#Problem_13| 2006 AIME I Problem 13]] | ||
| − | * Use of recursion to count a type of number: [[2007 AMC 12A | + | * Use of recursion to count a type of number: [[2007_AMC_12A_Problems#Problem_25| 2007 AMC 12A Problem 25]] |
| − | * Yet another use in combinatorics [[ | + | * Yet another use in combinatorics [[2008_AIME_I_Problems#Problem_11| 2008 AIME I Problem 11]] |
== See also == | == See also == | ||
Revision as of 13:01, 22 October 2014
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
