Difference between revisions of "Recursion"
m |
(added first example problem) |
||
| Line 2: | Line 2: | ||
Often, it is convenient to convert a recursive definition into a closed-form definition. For instance, the sequence defined recursively by <math>\displaystyle a_0 = 1</math> and <math>a_n = n\cdot a_{n - 1}</math> for <math>n > 0</math> also has the closed-form definition <math>\displaystyle a_n = n!</math> (where "!" represents the [[factorial]] function). | Often, it is convenient to convert a recursive definition into a closed-form definition. For instance, the sequence defined recursively by <math>\displaystyle a_0 = 1</math> and <math>a_n = n\cdot a_{n - 1}</math> for <math>n > 0</math> also has the closed-form definition <math>\displaystyle a_n = n!</math> (where "!" represents the [[factorial]] function). | ||
| + | |||
== Examples == | == Examples == | ||
| + | * [[Mock_AIME_2_2006-2007/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]] | ||
* 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]] | ||
| − | + | ||
| + | == See also == | ||
* [[Combinatorics]] | * [[Combinatorics]] | ||
* [[Sequence]] | * [[Sequence]] | ||
* [[Induction]] | * [[Induction]] | ||
Revision as of 12:16, 25 July 2006
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
