Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Recursion"

m (added internal links)
(→‎Examples)
 
(25 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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Recursion&oldid=209397"