Difference between revisions of "Recursion"

(categories)
m (WotW)
Line 1: Line 1:
 +
{{WotWAnnounce|week=Jan 17-23}}
 +
 
'''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.
 
'''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.
  

Revision as of 12:36, 17 January 2008

This is an AoPSWiki Word of the Week for Jan 17-23

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 = n\cdot a_{n - 1}$ for $n > 0$ also has the closed-form definition $a_n = n!$ (where "!" represents the factorial function).


Examples


See also