Recursion

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

Mock AIME 2 2006-2007 Problem 8 (number theory)
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

Page

Toolbox

Search

Recursion

Examples

See also