# Difference between revisions of "Recursion"

(rmv) |
(Changed factorial to a better example) |
||

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>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. | ||

− | Often, it is convenient to convert a recursive definition into a closed-form definition. For instance, the sequence defined recursively by <math>a_0 = 1</math> and <math>a_n = | + | Often, it is convenient to convert a recursive definition into a closed-form definition. For instance, the sequence defined recursively by <math>a_0 = 1</math> and <math>a_n = 2\cdot a_{n - 1}</math> for <math>n > 0</math> also has the closed-form definition <math>a_n = 2^n</math>. |

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. | 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. |

## Revision as of 23:35, 23 February 2008

**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 .

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

- Mock AIME 2 2006-2007 Problem 8 (number theory)
- A combinatorical use of recursion: 2006 AIME I Problem 11
- Use of recursion to compute an explicit formula: 2006 AIME I Problem 13
- Use of recursion to count a type of number: 2007 AMC 12A Problems/Problem 25