Difference between revisions of "Recursion"
m (fixed some LaTeX) |
m (proofreading) |
||
| Line 1: | Line 1: | ||
| − | '''Recursion''' is defining something in terms of a previous term, function, etc. For example, the famous [[Fibonacci sequence]] is defined recusively. If we let <math>F_n</math> be the nth term, the sequence is: <math>\displaystyle F_0=1, F_1=1, F_2=2, F_3=3, F_4=5, F_5=8</math>, and so on. A | + | '''Recursion''' is defining something in terms of a previous term, function, etc. For example, the famous [[Fibonacci sequence]] is defined recusively. If we let <math>F_n</math> be the nth term, the sequence is: <math>\displaystyle F_0=1, F_1=1, F_2=2, F_3=3, F_4=5, F_5=8</math>, and so on. A recursive definition is: <math>F_{n+1}=F_{n}+F_{n-1}</math>. That is a symbolic way to say "The next term is the sum of the two previous terms". |
== Examples == | == Examples == | ||
Revision as of 12:57, 19 June 2006
Recursion is defining something in terms of a previous term, function, etc. For example, the famous Fibonacci sequence is defined recusively. If we let 
be the nth term, the sequence is: 
, and so on. A recursive definition is: 
. That is a symbolic way to say "The next term is the sum of the two previous terms".
Examples
- A combinatorical use of recursion: AIME 2006I/11
- Use of recursion to compute an explicit formula: AIME 2006I/13
See also
- [Combinatorics]
