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"

(See also)
(Undo revision 99737 by Cognac (talk))
(Tag: Undo)
Line 20: Line 20:
 
* [[Sequence]]
 
* [[Sequence]]
 
* [[Induction]]
 
* [[Induction]]
 +
* [http://artofproblemsolving.com/wiki/index.php?title=Recursion Recursion]
  
 
[[Category:Combinatorics]]
 
[[Category:Combinatorics]]
 
[[Category:Definition]]
 
[[Category:Definition]]

Revision as of 09:29, 25 December 2018

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