Difference between revisions of "Recursion"
m (internalized links) |
m |
||
Line 5: | Line 5: | ||
== Examples == | == Examples == | ||
− | * A combinatorical use of recursion: [[2006_AIME_I_Problems#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]] | + | * Use of recursion to compute an explicit formula: [[2006_AIME_I_Problems#Problem_13| 2006 AIME I Problem 13]] |
=== See also === | === See also === |
Revision as of 11:01, 14 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
- A combinatorical use of recursion: 2006 AIME I Problem 11
- Use of recursion to compute an explicit formula: 2006 AIME I Problem 13