Recursion
Penjee.com, a site for teaching kids Python, has some excellent gifs on Recursion in programming including this one:
What is a recursive Sequence?
A Recursive Sequence is a function that refers back to itself. Below are several examples of recursive sequences.
For instance, $$ \color{red}{f}(x) = \color{red}{f}(x-1) + 2 $$ is an example of a recursive sequence because $$ \color{red}{f}(x)$$ defines itself using $$ \color{red}{f}$$ .
Visualization of a Recursive sequence
Pascal's Triangle is one of the most famous recursive sequences in mathematics. Below is a visualization of how Pascal's Triangle works. As you can see each term in the triangle is a result of adding two other 'parts' of the triangle.See more math gifs here
Example 1
Calculate $$ f(7)$$ for the recursive sequence $$ f(x) = 2 \cdot f(x - 2) +3$$ which has a seed value of $$f(3) = 11 $$
Example 2
Calculate $$ f(8)$$ for the recursive sequence $$ f(x) = 4 \cdot f(x - 3) + 1 $$ which has a seed value of $$f(2) = 9 $$
The Two "Phases" of solving recursion problems
- Phase I: Re-subsitute values into $$ f(x) $$ until you reach the "seed value" (in programming it's often called the "base case")
- Part II: Once you reach the Seed Value you start resubstituting values into the earlier expressions (back up the chain). The key here is is that you are substituting actual numbers/values now.
Can you determine why the sequence below is 'unsolvable'?
Look at the problem step by step to see why you cannot solve this problem.
Example 3
This example is one of the most famous recursive sequences and it is called the Fibonacci sequence. It also demonstrates how recursive sequences can sometimes have multiple $$ f(x)$$'s in their own definition.It is defined below
$$ f(x) = f(x-1) + f(x-2) $$
Keep re-substituting until you reach the seed value ( $$ f( \color{red}{4}) = \color{blue}{2}$$)
Substitute back up the "chain" using actual values
Below is the step by step work
$$ \boxed{ f( \color{red}{6}) = 2\cdot f( \color{red}{5} )+3 \\ f( \color{red}{6}) = 2 \cdot \color{blue}{7} +3 = \color{blue}{17} } \\ \boxed{ f( \color{red}{5}) = 2\cdot f( \color{red}{4}) +3 \\ f( \color{red}{5}) = 2 \cdot \color{blue}{2} +3 = \color{blue}{7} } \\ \boxed{ f( \color{red}{4}) = \color{blue}{2} } $$Keep re-substituting until you reach the seed value ( $$ f( \color{red}{12}) = \color{blue}{-4}$$)
Substitute back up the "chain" using actual values
Below is the step by step work
$$ \boxed{ f( \color{red}{8}) = 5\cdot f( \color{red}{10 } ) - 3 \\ f( \color{red}{8}) = 5\cdot \color{blue}{-23} - 3= -93 } \\ \boxed{ f( \color{red}{10 }) = 5\cdot f( \color{red}{12}) - 3 \\ f( \color{red}{10 }) = 5\cdot \color{blue}{-4} - 3= -23 } \\ \boxed{ f( \color{red}{12}) = \color{blue}{-4} } $$Keep re-substituting until you reach the seed value ( $$ f( \color{red}{0}) = \color{blue}{2}$$)
Substitute back up the "chain" using actual values
Below is the step by step work
$$ f( \color{red}{x+1}) = -2\cdot f(\color{red}{x}) + 3 \\ \boxed{ f( \color{red}{2}) = -2 \cdot f( \color{red}{1} + 3 \\ f( \color{red}{2}) = -2 \cdot \color{blue}{ -1 } ) + 3 = 5 } \\ \boxed{ f( \color{red}{1}) = -2 \cdot f( \color{red}{0} ) + 3 \\ f( \color{red}{1}) = -2 \cdot \color{blue}{ 2 } + 3 = -1 } \\ \boxed{ f( \color{red}{0 }) = \color{blue}{ 2 } } $$Keep re-substituting until you reach the seed value ( $$ f( \color{red}{1}) = \color{blue}{5}$$)