Difference between revisions of "Recursion"
m (added internal links) |
|||
| 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>\displaystyle 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>\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). | 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). | ||
Revision as of 22:47, 22 June 2006
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 
be the 
th Fibonacci number, the sequence is defined recursively by the relations 
and 
. (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: 
, and so on.
Often, it is convenient to convert a recursive definition into a closed-form definition. For instance, the sequence defined recursively by 
and 
for 
also has the closed-form definition 
(where "!" represents the factorial function).
Examples
- A combinatorical use of recursion: AIME 2006I/11
- Use of recursion to compute an explicit formula: AIME 2006I/13
