## Here's a mystery sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, X, Y¶

### Based on this pattern, see if you can you figure out the next two terms: X and Y.¶

In [2]:
def f(n):
if n <= 2: return 1
else: return f(n-1)+f(n-2)

In [3]:
print([f(1),f(2),f(3),f(4),f(5),f(6),f(7),f(8),f(9),f(10),f(11),f(12),f(13),f(14),f(15)])

[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]

In [4]:
print([f(5),f(10),f(15),f(20),f(25)])

[5, 55, 610, 6765, 75025]


# Counting Routes Problem¶

## Let's count the number of routes from the bottom-left square to the top-right square¶

### Solve this problem for both the 4x4 board and the 5x5 board¶

In [1]:
def routes(x,y):
if x == 1:
return 1
elif y == 1:
return 1
else:
return routes(x-1,y)+routes(x,y-1)

In [9]:
routes(8,8)

Out[9]:
48620
In [31]:
for x in (5,4,3,2,1):
print([routes(x, y) for y in [1,2,3,4,5]])

[1, 5, 15, 35, 70]
[1, 4, 10, 20, 35]
[1, 3, 6, 10, 15]
[1, 2, 3, 4, 5]
[1, 1, 1, 1, 1]


# Real-Life Applications of Recursion¶

## We are solving hard problems by combining solutions to problems we've already solved.¶

### See if you can figure out all the ways that recursion is used in the following video.¶

In [10]:
from IPython.display import YouTubeVideo