Recursion, the Fibonacci Sequence and Memoization || Python Tutorial || Learn Python Programming


bunnies love one another a lot if you put a pair of rabbits in a vast field covered in fresh grass they will reproduce like mad the number of fluffy pairs grows according to the Fibonacci sequence to write a function giving the terms of the Fibonacci sequence you will need recursion to make this function efficient we will use memorization let’s get ready to count bunnies the first few terms of the Fibonacci sequence are 1 1 2 3 5 8 13 21 here is how the sequence is constructed the first two terms are ones thereafter each term is the sum of the previous two terms one plus one is two the third term one plus two equals three the fourth term two plus three is five three plus five is eight five plus eight is thirteen and 8 plus 13 is twenty-one this process continues forever our goal is to write a function returning the emptor m– of the Fibonacci sequence our function should be fast clearly written and rock solid you may think this will be simple but by the time we are done with our function it will be more complex than you may expect by the way some people argue that the sequence should start with 0 and 1 if you encounter this situation don’t panic other than the zero the two sequences are identical people love to debate the smallest of details let’s now write the function we begin by giving our function a name we will follow the Python style guide and use all lowercase letters for the name of our function there is a single input n this function will return the emptor m– to begin we handle the starting cases if N equals one we return the first term one if N equals two we return the second term 1 if n is larger than two we return the sum of the previous two terms because this function is calling itself we call it a recursive function let’s test this function to see if it works we will print the first 10 terms notice that our range is from 1 to 11 not 1 to 10 that is because the range function does not include the final number frustrating I know now run our function worked does this mean we are done before we move on let’s test our function for a few more values what if we display the first 100 terms of the Fibonacci sequence run well this is disappointing our function is slowing down it’s virtually useless beyond a few dozen terms why is this and how can we fix this to see why this function is so slow look what happens when it computes the 5th term of the sequence because this is a recursive function Fibonacci 5 returns Fibonacci 4 plus Fibonacci three but Fibonacci 4 returns Fibonacci 3 plus Fibonacci 2 and Fibonacci 3 equals Fibonacci two plus Fibonacci 1 but now the function must make another recursive call because Fibonacci 3 equals 4 Bonacci 2 plus Fibonacci 1 our poor computer is repeating itself needlessly since Fibonacci 1 and Fibonacci 2 are both 1 we finally get the answer 5 our simple recursive function is careless we are making it repeat itself over and over and over and over there is a simple cure to this madness memoization the idea behind memorization is simple store the values for recent function calls so future calls do not have to repeat the work there are several ways to do this in Python we will first implement memorization explicitly so you can see how it works then we will use a built-in Python tool that makes memoization trivial to begin create a dictionary called fibonacci cache which will store recent function calls next let’s rewrite the Fibonacci function to make use of cached values the first thing we will do is check to see if the value for the nth term is in our cache if it is then simply return it otherwise we must compute the nth term but we will handle this differently than before we do not want to simply return the value instead we will first compute the value cache it then return it we compute the nth term the same as before the first and second terms are both 1 otherwise we make a recursive call to compute the nth term finally store the return value in our fibonacci cache dictionary then return it let’s see if this function performs better than our first attempt much better let’s really put this function to the test and display the first 1,000 terms impressive now that you have seen an explicit implementation of memorization I would like to show you a simpler approach for this let’s return to our first version of the function this function is appealing it is clean and simple from the func tools module import a decorator called LRU cache this stands for least recently used cache and it provides a one-line way to add memorization to your functions to use this right at LRU cache before our function in parentheses enter the number of values to cache by default Python will cache the 128 most recently used values so if you do not specify a max size you will still see benefits our original function will now operate very quickly as proof let’s print the first 500 values much better a simple function with fast performance but our work is not done what if we call the function and pass in the value to point 1 or negative 1 or the string 1 in all cases the function did not know what to do that is because we did not first check that the argument was a positive integer let’s fix this first check that the input is an integer if it is of the wrong type then raise a type error telling the user what argument is expected next verify that the argument is a positive integer if not raise a value error with the same message now if we call our fibonacci sequence with a float non positive integer or any other forbidden value the user will receive a helpful error message by the way there are many ways this method can be shortened but we have opted for clarity over compactness short and clever code can be fun to write but it often torments others let’s take a final look at the first 50 Fibonacci numbers as you can see the numbers grow quickly in size but how quickly to see we will compute the ratio between consecutive terms interesting the ratio between consecutive terms in the Fibonacci sequence appears to converge to a number in fact the ratios converge to the golden ratio you can learn more about this in our video on the Fibonacci sequence and the golden ratio like rabbits recursive functions can quickly take over caution must be exercised otherwise like Fibonacci you will end up with a fuzzy-wuzzy mess on your hands

100 thoughts on “Recursion, the Fibonacci Sequence and Memoization || Python Tutorial || Learn Python Programming

  1. The short and sweet format is a great addition to Python instruction tutorials.
    … and very sexy thanks! …

  2. *just wow*.. impossible to lose focus watching this video, didn't even check my phone in 8 minutes

  3. one of THE best videos i ve learned from. and that too, keeping my interest in it, throughout.

  4. I am curious, wouldn't this work?
    list_1=[0,1]

    for x in range(2,1000):

    if x not in list_1:

    list_1.append(list_1[-1]+list_1[-2])

    print(list_1)

  5. Simple, elegant and pythonic tutorials.

    while True:
    view = subprocess.Popen(socratica.videos[0:-1])

  6. you are AWESOME ! . one small correction

    fib_cache = {}
    def fibbonacci(n):
    if n in fib_cache:
    return fib_cache[n]

    wont work it should be
    def fibbonacci(n):

    if n <= len(fib_cache):
    return fib_cache[n]

  7. awesome video!
    but why are we using recursion in fibonacci instead of just using a for loop with a, b = b, a+b and print?

  8. The only python series, and perhaps any educational or just anything, which is not getting fewer and fewer views by every next video. This is amazing.
    This video is hella useful. Very interesting, smart and just superb.

  9. I have a question: While checking for a positive integer, instead of the "if" control structure, why not use the built-in "assert" keyword, because it requires fewer lines of code.
    assert type(n)==int and n> 0,"n must be a positive integer"
    Like so.

  10. Your English is good, i appreciate that, but.., you don't have to talk so serious about it. PLEASE! LADY COMPUTER SOCKET DRESS!!!

  11. Wow! Socratica.. Youtube should come up with Claps feature to replace the like button similar to Medium. Cuz this tutorial video deserves more than just like. 😛

  12. How did she do this with a straight face on ? I'd laugh every five minutes I had to read it in that "A.I" voice

  13. Amazing channel. Please make videos on data structures and algorithms… Can't go back to school again!

  14. This function i whipped up seems pretty quick. This is fun stuff to play with to learn python! Thanks for the video!
    # this returns the nth fibonacci sequence quickly
    def fib(nth: int, print_work: bool = False):
    a = 1
    b = 1
    c = 2
    # loop 100 times
    for iteration in range(1, nth+1):
    c = a + b
    b = a
    a = c
    if print_work:
    print(a, b, c)

    if nth == 1:
    return 1
    elif nth == 2:
    return 1
    else:
    return c

  15. Never under-estimate what you are doing for any second…. you are really changing lives and bringing hope to the humanity.

  16. I would have become a straight A in college if I had instructors in college that looked like her.

  17. @ 1:34 If you've ever raised rabbits, you will know that they reproduce at a FAR faster rate than the fibonacci sequence.

  18. When i clicked on this video i first felt like a spy receiving it's top secret mission haha. But the video was very helpful, thank you!

  19. I really love your video's. However i cannot find the golden ratio video on your YT account

  20. great stuff. but why use a function that can be implemented iteratively much faster and easier?

  21. the first two term of Fibonacci are 0,1 not 1,1 just for the record

  22. Well then, nobody wants a "fuzzy wuzzy mess on their hands". Heh.

  23. Here's the Fibonacci function without cache:

    def fibonacci(n):
    a = 0
    b = 1
    if n < 0:
    print("Incorrect input")
    elif n == 0:
    return a
    elif n == 1:
    return b
    else:
    for i in range(1,n):
    c = a + b
    a = b
    b = c
    return b

    for i in range(1, 1001):
    print(i, fibonacci(i))

  24. Love these videos, despite using python all the time, I learn something new every video just awesome.
    One optimization I would recommend though is for handling type errors would be to use a try catch exception block.

    So instead of:
    if type(n) != int:
    raise …

    if n > 1:
    raise …

    you instead could do :
    @lru_cache(maxsize = 1000)
    def fib(n):
    try:
    if n == 1:
    return 1
    elif n == 2:
    return 1
    elif n > 2:
    return fib(n-1) + fib(n-2)
    #This is added because negative numbers do not thrown an exception naturally
    elif n < 1:
    raise ValueError("n must be a positive int")
    #This catches all other shown cases
    except (TypeError):
    raise TypeError("n must be a positive int")

    This will instead allow the code to run without checking the data before hand. So successful calls do not have an added check. It is only if it fails to meet the previous if statements or throws an TypeError exception.

  25. WTF just happened, is this code magic????
    How did…
    What did…
    The def function didn't write anything, any equations, and it worked! It works as how we humans perceive fibonacci sequence.

    I mean… how???
    Everybody writes this down by doing value switching like
    a = b
    b = a + b
    c = a + b

    But this….

    It's so damn clean and so damn clarified. I am amazed by the high precision, almost like a robot, anchor lady's way of doing this algorithm.

    This is so cool.

  26. the way u teach makes me feel like i really need to understand it or you will kill me somehow. i do understand it tho xD

  27. All you wierdo pervs that are trying to hit on an AI bot, well I got a question for you.
    WHAT THE SHIT IS WRONG WITH YOUR BRAIN??

  28. "maxsize" argument doesn't have to be 1000. It can be set to 3 in case of fibonacci function. Because there's no need to cache all "least recently used " values. We just need last 3 values (I initially thought we need 2 values only, but maxsize=3 gives the desired result. Not sure why)

  29. Nunca había visto el fibonacci rexursivo solucionado de otra manera (con aquello de memoization). Genial

  30. def recurse(i): # This tells you why recursion is not the best idea if you run it.
    i += 1
    print(i)
    recurse(i)
    recurse(0)

    def recurse(i): # This tells you at what point recursion is not the best idea.
    i += 1
    print(i)
    try:
    recurse(i)
    except:
    pass
    recurse(0)

    # no exit() needed, both will error.

  31. Could someone please explain what (n-1) and (n-2) do? Thank you!

  32. It slows down for me when it gets to 38 using the Lru_cache method.

  33. That deadpan delivery makes this learning experience the best I've ever had.

  34. Very good!
    I'm don't speak english, but I'm ready the legends… I'm from Brasil.

    Please, make more videos with legends!

    Excusime for gramatycals erros.

  35. The way you check the type isn't the best. You should use isinstance(n, int) (or, in Python 2, isinstance(n, (int, long)) ).. This is better for a variety of reasons. I'm a bit surprised as you normally write impeccable Python.

  36. Thank you for providing high-quality videos with the feature of science fiction. I love your teaching style: clear and easy to understand.

  37. If computers could feel pain, that first recursive Fibonacci Sequence probably would have hurt :/. Great series btw!

  38. what about this?

    def fibonacci(n):
    a, b = 0, 1
    while(a < n):
    a, b = b, a+b
    print(a)
    print()

    x=100
    fibonacci(x)

  39. to be honest i did not really find it helpful. she could come with an easy example but i don'[t what the hell she is on about?

  40. Support what you love! Socratica has a Kickstarter to make more Python: http://bit.ly/PythonKickstarter

  41. I understand much more things fro this video , but This code return nothing,print nothing

  42. Not recommending this channel, this time she didn't write a docstring for the fibonacci function

  43. This video is really good and I've been asked to write a fib function at 4 job interviews; including a job interview to work on Google Chrome.

    The solution given in the video with memoization is pretty good (and probably good enough for many jobs), especially if you can explain it's computational complexity. BUT if want to knock it out of the park, then consider learning how to write a Fibonacci function implemented with fast matrix exponentiation. It will take your worst case from O(n) with the memoized solution to O(log2 n)… assuming all integer arithmetic can happen in constant time (which is a bad assumption because the computer can't do integers arithmetic in constant time once the numbers get huge)…

    Here's my dumb solution (yours can be better using tricks from the video or from math):

    def fibonacci(n):
    if n == 1:
    return 1
    elif n == 2:
    return 1
    else:
    base = [[1, 1], [1, 0]]
    vec = [1, 0]
    matrix = fast_matrix_exp(base, n – 1)
    solution_vector = matrix_vec_mult(matrix, vec)
    return solution_vector[0]

    def fast_matrix_exp(matrix, exponent):
    if exponent == 1:
    return matrix

    part = fast_matrix_exp(matrix, exponent >> 1)
    result = matrix2x2_mult(part, part)
    if exponent % 2:
    result = matrix2x2_mult(result, matrix)
    return result

    # Usually a job interview won't make you write this tedious stuff that follows, but I included it so you can actually run this

    def matrix2x2_mult(a, b):
    a_row0 = row(a, 0)
    a_row1 = row(a, 1)
    b_col0 = col(b, 0)
    b_col1 = col(b, 1)
    a = sum_elementwise_mult(a_row0, b_col0)
    c = sum_elementwise_mult(a_row1, b_col0)
    b = sum_elementwise_mult(a_row0, b_col1)
    d = sum_elementwise_mult(a_row1, b_col1)
    return [[a, b], [c, d]]

    def matrix_vec_mult(matrix, vec):
    a = sum_elementwise_mult(row(matrix, 0), vec)
    b = sum_elementwise_mult(row(matrix, 1), vec)
    return [a, b]

    def row(matrix, row_number):
    return matrix[row_number]

    def col(matrix, col_number):
    return [matrix[0][col_number], matrix[1][col_number]]

    def elementwise_mult(v1, v2):
    return [v1[0]*v2[0], v1[1]*v2[1]]

    def sum_elementwise_mult(row, col):
    return sum(elementwise_mult(row, col))

    #Hope this helps

Leave a Reply

Your email address will not be published. Required fields are marked *