## Recursion – Recursive Definitions

Infinite sequences can often be defined in a recursive way. Every recursive definition needs a base case defining the first values in the sequence (at least one) and the rule for forming an element using previously computed ones.

Below are some examples:

Powers of 2

• 1, 2, 4, 16, 32, 64, …., 2n, …
• Base case: P(0) = 1, P(1) = 2
• P(n) = 2 x P(n-1)

An arbitrary sequence

Factorials

• n! is the product of all positive integers less than or equal to n.
• For example, 5! = 5 x 4 x 3 x 2 x 1 = 120
• Base case:  F(1)=1
• F(n) = n x F(n-1) for n >1
• Interesting facts and uses of factorials can be found at http://www.mathsisfun.com/numbers/factorial.html.

Fibonacci sequence

• 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, …
• Base cases: f(0)=0 and f(1)=1
• f(n) = f(n-1) + f(n-2) for n>1
• we describe different ways computing f(n) in Example 5: Computing a Fibonacci number.
• Interesting information and historical facts about Fibonacci numbers can be found at

Exercises a teacher can do with students

• For Fibonacci numbers, ask students to compute a specified value, like f(15) , with paper and pencil. Let them find their own way of doing it and ask them to explain how the managed the results computed. Did they use recursion?
• Give students a sequence and ask them to determine the recursive definition generating the sequence. For example
• 1, 3, 9, 27, 81, 243, ….
• 1, 7, 49, 343, …