12.1. Recursion http://www.ck12.org
12.1 Recursion
Here you will define patterns recursively and use recursion to solve problems.
When you look at a pattern, there are many ways to describe it. You can describe patterns explicitly by stating how
each termakis obtained from the term numberk. You can also describe patterns recursively by stating how each
new termakis obtained from the previous termak− 1. Recursion defines an entire sequence based on the first term
and the pattern between consecutive terms. The Fibonacci sequence is a famous recursive sequence, but how is it
represented using recursion?
0 , 1 , 1 , 3 , 5 , 8 , 13 , 21 , 34 ,...
Watch This
MEDIA
Click image to the left for use the URL below.
URL: http://www.ck12.org/flx/render/embeddedobject/62257http://www.youtube.com/watch?v=RjsyEWDEQe0 James Sousa: Finding Terms in a Sequence Given the Recursive
Formula
Guidance
When most people see a pattern they see how consecutive terms are related to one another. You might describe
patterns with phrases like the ones below:
TABLE12.1:
Pattern Recursive Description
3 , 6 , 12 , 24 ,... “Each term is twice as big as the previous term”
3 , 6 , 9 , 12 ,... “Each term is three more than the previous term”Each phrase is a sign of recursive thinking that defines each term as a function of the previous term.
ak=f(ak− 1 )In some cases, a recursive formula can be a function of the previous two or three terms. Keep in mind that the
downside of a recursively defined sequence is that it is impossible to immediately know the 100thterm without
knowing the 99thterm.
Example A
For the Fibonacci sequence, determine the first eleven terms and the sum of these terms.