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

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

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

Let’s explore recursion by writing a function to generate the terms of the Fibonacci sequence. We will use a technique called “memoization” to make the function fast. We’ll first implement our own caching, but then we will use Python’s builtin memoization tool: the lru_cache decorator.

➢➢➢➢➢➢➢➢➢➢
To learn Python, you can watch our playlist from the beginning:

➢➢➢➢➢➢➢➢➢➢
We recommend:
Python Cookbook, Third edition from O’Reilly

The Mythical Man Month – Essays on Software Engineering & Project Management

Shop Amazon Used Textbooks – Save up to 90%

➢➢➢➢➢➢➢➢➢➢
Subscribe to Socratica:

To support more videos from Socratica, visit
Socratica Patreon

Socratica Paypal

We also accept Bitcoin! 🙂

➢➢➢➢➢➢➢➢➢➢
Python instructor: Ulka Simone Mohanty
Written & Produced by Michael Harrison
FX by Andriy Kostyuk

source

By |2019-08-20T22:12:59+00:00August 20th, 2019|Python Video Tutorials|40 Comments

1. Datascience Concepts August 20, 2019 at 10:13 pm - Reply

Very well explained!

2. Grego Murunga August 20, 2019 at 10:13 pm - Reply

This human ai is amazing

3. Jeroen Strompf August 20, 2019 at 10:13 pm - Reply

Wonderful video!

4. Nilton Duarte August 20, 2019 at 10:13 pm - Reply

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.

Impressive videos 👍

6. J J August 20, 2019 at 10:13 pm - Reply

"cleaver code is fun to write, but it torments others…" Hahahaahah

7. rwny August 20, 2019 at 10:13 pm - Reply

Impressive ..

8. Mike Martin August 20, 2019 at 10:13 pm - Reply

Let’s get ready- to count bunnies. I love it.

9. Xinghong He August 20, 2019 at 10:13 pm - Reply

what does "now, run" mean?

10. Rafael Peres August 20, 2019 at 10:13 pm - Reply

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

11. Vishal svits August 20, 2019 at 10:13 pm - Reply

I love you. From India

12. TechWizPC August 20, 2019 at 10:13 pm - Reply

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

13. ZyptosKid August 20, 2019 at 10:13 pm - Reply

why is she so extra

14. willzurmacht August 20, 2019 at 10:13 pm - Reply

I just discovered this now. This channel is amazing!!

15. Yasir Ali August 20, 2019 at 10:13 pm - Reply

i wonder if she ever smile. 😐

16. Khoa Cao August 20, 2019 at 10:13 pm - Reply

thanks

17. socialytiks dev August 20, 2019 at 10:13 pm - Reply

super

18. John Smith August 20, 2019 at 10:13 pm - Reply

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

19. leathernluv August 20, 2019 at 10:13 pm - Reply

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.

20. Gerald Bustos August 20, 2019 at 10:13 pm - Reply

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

21. Rajorshi Roy August 20, 2019 at 10:13 pm - Reply

"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)

22. Martinatious Janko August 20, 2019 at 10:13 pm - Reply

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??

Keep up

24. Tabura August 20, 2019 at 10:13 pm - Reply

OMG

25. Mahteen Bash August 20, 2019 at 10:13 pm - Reply

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

26. erick shuffer August 20, 2019 at 10:13 pm - Reply

2:26 you read my heart Socratica!

27. EverR32 August 20, 2019 at 10:13 pm - Reply

So clever!

28. VIRENDER SHARMA August 20, 2019 at 10:13 pm - Reply

NICE

29. Samouel Arghan August 20, 2019 at 10:13 pm - Reply

30. Eugene Rider August 20, 2019 at 10:13 pm - Reply

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.

31. Waitwhat469 August 20, 2019 at 10:13 pm - Reply

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.

if type(n) != int:
raise …

if n > 1:
raise …

@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.

32. Michael Hansen August 20, 2019 at 10:13 pm - Reply

Elegant in Scheme, ugly in Python.

33. C0LD August 20, 2019 at 10:13 pm - Reply

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))

34. Mark Hathaway August 20, 2019 at 10:13 pm - Reply

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

35. Sara Ayoub August 20, 2019 at 10:13 pm - Reply

I'd love a fuzzy wuzzy mess though

36. Mohamed Nashaat August 20, 2019 at 10:13 pm - Reply

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

37. Daniel der Wertvolle August 20, 2019 at 10:13 pm - Reply

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

38. Julian Kercsik August 20, 2019 at 10:13 pm - Reply

I

39. BronzeJourney August 20, 2019 at 10:13 pm - Reply

Clearly written and recursions? Hmm…

40. minibona August 20, 2019 at 10:13 pm - Reply