Difference between revisions of "Recursion"
(needs more content) |
(→Examples) |
||
| (35 intermediate revisions by 23 users not shown) | |||
| Line 1: | Line 1: | ||
| − | ''Recursion'' is ... | + | '''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 <math>F_n</math> be the <math>n</math>th Fibonacci number, the sequence is defined recursively by the relations <math>F_0 = F_1 = 1</math> and <math>F_{n+1}=F_{n}+F_{n-1}</math>. (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: <math>F_0=1, F_1=1, F_2=2, F_3=3, F_4=5, F_5=8</math>, and so on. |
| + | |||
| + | Often, it is convenient to convert a recursive definition into a closed-form definition. For instance, the sequence defined recursively by <math>a_0 = 1</math> and <math>a_n = 2\cdot a_{n - 1}</math> for <math>n > 0</math> also has the closed-form definition <math>a_n = 2^n</math>. | ||
| + | |||
| + | 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 == | == Examples == | ||
| − | * A | + | * [[Mock_AIME_2_2006-2007_Problems#Problem_8 | Mock AIME 2 2006-2007 Problem 8]] ([[number theory]]) |
| + | *[[1994_AIME_Problems/Problem 9|1994 AIME Problem 9]] | ||
| + | * A combinatorial use of recursion: [[2006_AIME_I_Problems#Problem_11|2006 AIME I Problem 11]] | ||
| + | * Another combinatorial 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 count a type of number: [[2007_AMC_12A_Problems#Problem_25| 2007 AMC 12A Problem 25]] | ||
| + | * Yet another use in combinatorics [[2008_AIME_I_Problems#Problem_11| 2008 AIME I Problem 11]] | ||
| + | * [[2015_AMC_12A_Problems#Problem_22| 2015 AMC 12A Problem 22]] | ||
| + | * [[2019_AMC_10B_Problems#Problem_25| 2019 AMC 10B Problem 25]] | ||
| + | * [[2004_AIME_I_Problems#Problem_15| 2004 AIME I Problem 15]] | ||
| + | |||
| + | == See also == | ||
| − | + | * [[Combinatorics]] | |
| + | * [[Sequence]] | ||
| + | * [[Induction]] | ||
| + | * [https://artofproblemsolving.com/wiki/index.php/Recursion Recursion] | ||
| − | + | [[Category:Combinatorics]] | |
| + | [[Category:Definition]] | ||
Latest revision as of 15:03, 1 January 2024
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)
- 1994 AIME Problem 9
- A combinatorial use of recursion: 2006 AIME I Problem 11
- Another combinatorial 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
- 2015 AMC 12A Problem 22
- 2019 AMC 10B Problem 25
- 2004 AIME I Problem 15
