During AMC testing, the AoPS Wiki is in read-only mode. Your account is not considered logged in on wiki pages and no edits can be made.

Difference between revisions of "Recursion"

(Examples)
 
(26 intermediate revisions by 17 users not shown)
Line 1: Line 1:
'''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>\displaystyle F_0=1, F_1=1, F_2=2, F_3=3, F_4=5, F_5=8</math>, and so on.
+
'''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.
  
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 ==
  
* A combinatorical use of recursion: [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=448525#p448525 AIME 2006I/11]
+
* [[Mock_AIME_2_2006-2007_Problems#Problem_8 | Mock AIME 2 2006-2007 Problem 8]] ([[number theory]])
* Use of recursion to compute an explicit formula: [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=449173#p449173 AIME 2006I/13]
+
*[[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 ===
+
== See also ==
  
 
* [[Combinatorics]]
 
* [[Combinatorics]]
 
* [[Sequence]]
 
* [[Sequence]]
 
* [[Induction]]
 
* [[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 $F_n$ be the $n$th Fibonacci number, the sequence is defined recursively by the relations $F_0 = F_1 = 1$ and $F_{n+1}=F_{n}+F_{n-1}$. (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: $F_0=1, F_1=1, F_2=2, F_3=3, F_4=5, F_5=8$, and so on.

Often, it is convenient to convert a recursive definition into a closed-form definition. For instance, the sequence defined recursively by $a_0 = 1$ and $a_n = 2\cdot a_{n - 1}$ for $n > 0$ also has the closed-form definition $a_n = 2^n$.

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

See also