alt text

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
YouTubeVideo('cdgQpa1pUUE')
Out[10]:

alt text

In [ ]: