Difference between revisions of "Recursion"
m (typo) |
(linked induction) |
||
Line 10: | Line 10: | ||
* [[Combinatorics]] | * [[Combinatorics]] | ||
* [[Sequence]] | * [[Sequence]] | ||
+ | * [[Induction]] |
Revision as of 17:35, 19 June 2006
Recursion is defining something in terms of a previous term, function, etc. For example, the famous Fibonacci sequence is defined recursively. 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