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)
(Examples)
 
(3 intermediate revisions by one other user not shown)
Line 9: Line 9:
  
 
* [[Mock_AIME_2_2006-2007_Problems#Problem_8 | Mock AIME 2 2006-2007 Problem 8]] ([[number theory]])
 
* [[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]]
 
* 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]]
 
* Another combinatorial use of recursion: [[2001_AIME_I_Problems#Problem_14| 2001 AIME I Problem 14]]
Line 23: Line 24:
 
* [[Sequence]]
 
* [[Sequence]]
 
* [[Induction]]
 
* [[Induction]]
* [http://artofproblemsolving.com/wiki/index.php?title=Recursion Recursion]
+
* [https://artofproblemsolving.com/wiki/index.php/Recursion Recursion]
  
 
[[Category:Combinatorics]]
 
[[Category:Combinatorics]]
 
[[Category:Definition]]
 
[[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