6. Recursion and Dictionaries

MIT 6.0001 Introduction to Computer Science and Programming in Python, Fall 2016
View the complete course: ocw.mit.edu/6-0001F16
Instructor: Prof. Eric Grimson
In this lecture, Prof. Grimson introduces the concept of recursion and the Python dictionary data type.
License: Creative Commons BY-NC-SA
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu

[@stephfong4577]

Prof. Grimson should teach Introduction to Algorithms. He is clear and articulate.

[@MrFaiqueShakil]

@@charge2snglrty409 kya hagg raha hai , har jagah...?

[@Tintak_hatpin]

@@MrFaiqueShakil hahaha

[@peterpace3379]

@@charge2snglrty409 Nahi bhai ye sab to nursery ke bachhe padhte hai -_-

[@snamburi3]

he teaches Intro to Computer Science and Programming course on EdX. It covers a few algorithms

[@leixun]

*My takeaways:* 1. What is recursion in the context of this lecture 3:47 2. An example: multiplication - iterative solution vs recursive solution 5:48 3. Recursion with one base case - factorial 9:25 4. Recursion with multiple base cases - Fibonacci numbers 24:38 4. Recursion on non-numerics 29:12 5. Dictionaries (mutable data structure contains "keys" and corresponding "values", it has no order, only matches "keys" to "values") 33:27 6. Key things about keys and values 39:10 7. List vs dictionaries 40:20 8. An example of using dictionaries 40:45 9. Efficient Fibonacci 46:18

[@emmaguo619]

Thank you so much! Ignore the racist!

[@leixun]

Emma Go thank you so much!

[@simenghan5897]

The part linking mathematical induction to recursion is genius. Thank you so much!

[@DanielFerreira-gu1di]

The way he teachs is awesome. Fun + Good Content!

[@shaileshrana7165]

More than what he taught, I loved how articulate and sure he was. Every word seemed measured. Lucky to get to experience this. Thank you MIT.

[@cryptonetcentralusa5592]

Prof. Grimson is one of my very best teachers! I've taken his Intro to Computer Science and Programming course on EdX and it was great! All his lectures here on KZbin are great, too! Thank you Professor and MIT!

[@manishahatzade1006]

Thank you Professor! Thank you MIT, I saw many youtube vids to understand recursion but this was the best explaination.

[@D_Analyst007]

I have seen many tower of hanoi and recursion videos, this one is just jewel! MIT has awesome teachers for any field! Prof Gilbert strang, John Tsitsiklis etc..

[@user-bc8jb3xf9y]

So even professors at MIT would first just run the exact same program again without changing anything when they meet a bug lol

[@georgikostov6982]

This one is a bit not sure if it works or not ... I guess he losted already.

[@obli8984]

that's what I also thought😀

[@genealso6726]

People like this should open their own school. Truly amazing professor, no wonder CS grads from MIT are so talented.

[@AnmolKumar-dh3lh]

Thank you teacher! I am grateful for all the efforts you took to prepare all the material for this class.

[@shreyapatel4127]

He is utterly crystal clear in what he says. Wow!

[@stephenc9398]

Great teacher but missed a great opportunity to use my favourite computer science joke: In order to understand recursion, one must first understand recursion.

[@RocknRollDina]

because its not a funny "joke"

[@stephenc9398]

@@RocknRollDina You are a funny joke

[@RocknRollDina]

@@stephenc9398 No I'm not, actually. Try again. You're bad at insults also.

[@federicofraguglia6773]

Don't listen to them... I found this joke amusing.

[@Raghav1205]

Because there is no base case

[@Rogues4Ever]

Best explanation of recursion I have watched to date. Thank you sir!

[@andycalderon8422]

This teacher was my first intro to python on Edx. He's awesome.

[@hdsmsmart]

which course is it ?

[@user-kv8oh8lx7y]

@@hdsmsmart the same course but on mit platforme

[@androtech7885]

The last two codes went over my head.

[@ucanhly1166]

I'm from Vietnam and live in hanoi but I've never heard about that story. It's really interesting.Thank for your dedicating lecture.

[@ali51717]

After this Lecture, I understand 2 things, Recursion and Why MIT is rated 1st in the world in Electrical engineering and computer science

[@wanyinleung912]

And the third thing is all cs jokes are bad.

[@gold9994]

@@charge2snglrty409 I did, because back in my first year, i skipped a lot of csc class in mit (even though I took Chemistry). My laptop was (and still) a gaming laptop, It's not convenient to bring it everywhere.

[@bee_irl]

34:13 is why MIT is on top. B is a failing grade, sorry, Ana.

[@cybern9ne]

I went to WVU. I learned the same subjects. It's not the material it's the student.

[@changding4355]

Nope, I'm from Berkeley EECS, I disagree with your second thing.

[@mouleeswarkothandaraman7095]

I finally found my base case for understanding recursion after searching recursively :)

[@12EdinAb]

i see what u did there

[@user-fl7vs4ed6l]

pre labeling ​​0:00:00 0:02:31​ 0:04:00 What is Recursion 0:05:58 Iterative algorithm so far 0:05:58 Multiplication iterative solution 0:07:56 0:09:49 Factorial 0:12:03 Recursive function scope example ​0:13:46​ Some observation 0:16:07 0:18:03 Example of induction 0:19:44 ​​0:23:12 Hanoi tower 0:24:56 ​Recursion with multiple base cases 0:26:14 Fibonacci 0:28:06​ 0:30:23 ​Solving recursively 0:33:52 How to store student info 0:35:45 ​0:36:00 ​0:38:00​ 0:40:25 Dict v.s. List 0:41:52 Creating a dictionary 0:43:02 ​0:44:16 ​0:45:16 ​0:46:25​

[@djangoworldwide7925]

What about ana jokes?

[@yukeyang5735]

Can't help applaud for the professor as he finished explaining the Hanna Tower problem.Brilliant!

[@vu_derArchitekt]

Hanoi Tower not Hanna :)

[@yukeyang5735]

You're right.Thanks for the correction.

[@Camelold]

Really really explanation of recursive. This is the best explanation I ever see. The math induction makes it even clearer and more interesting. And I enjoyed all the jokes.

[@spyinsecret0075]

I love the professor way of teaching!

[@scorpio19771111]

The clarity with which recursion was taught in this lecture, was blinding.

[@RyanScarbrough]

Complex yet really well explained, thanks!

[@FINSuojeluskunta]

I've always struggled with recursion besides the simple ones. Hopefully this makes it easier in the future

[@alinaust2452]

This is the clearest explanation I came across! Thanks so much!

[@craigdanielmaceacher]

If you are having trouble with recursion, don't worry most people have trouble with it--look up explanations from several sources besides this one, and one particular metaphor or walkthrough will eventually give you that a-ha moment where you now intuitively understand it. I didn't think he explained recursion well here, from point of view of someone without a science/math background; it wasn't until I researched it myself and watched videos showing how it worked graphically/metaphorically that I then understood it. TLDR: search of many recursion explained videos on YT, there's tons, and one of them will eventually click!

[@ChandravijayAgrawal]

He is narendra modi, what could you expect

[@theLowestPointInMyLife]

I agree, i already knew recursion and i didnt think this was explained well at all.

[@akshaykumart.r.3523]

@@ChandravijayAgrawal

[@DingusKhan42]

Excellent lecture and lecturer. Thanks for posting this.

[@aymensekhri2133]

Thanks a lot Prof. Eric !

[@pfever]

At MIT they teach new concepts introducing formal definitions followed by mathematical examples. At Stanford the introduce concepts first with easy to understand definitions or analogies and later reinforce the concepts with tons of practical examples.

[@boysen01]

Great material and a very good intro to recursion. Beware of typo in palindrome at 31:08

[@julio1148]

I want this man's presentation skills/confidence

[@xXZian6Xx]

For all my life, I have never found a lecturer this good.

[@TheVertical92]

check out CS50 from Havard.

[@kenmeyer100]

then you haven't met Grant Sanderson (3blue1brown on youtube)

[@xXZian6Xx]

@@kenmeyer100 i have, Grant is good at visualizing things, but not so much on explaining it like this prof

[@user-nq5wb1cz5e]

Great professor

[@RandomShowerThoughts]

this professor is insanely good at what he does

[@BlackhandYsmira]

I wish he gave all the lectures for this course, thank you for sharing these!

[@hamzafarooq7864]

Thanks ...content is superb...Recursion is explained in a brilliant way.

[@ramazanaktas3699]

About the game around 21:00 ; while moving around, there should be no greater disc *above* any disc, otherwise it is utterly simple: start to move from the smallest to spare, move the largest to the target destination and move the rest in the same fashion you did.

[@vincenr8822]

Thank you so much. This is amazing.

[@iphoneultra]

thank you MIT

[@pidusredlah]

This guy is so hilariously good. Understandable, given MIT.

[@mohammedabadirleencahararg9974]

nice teacher ur teaching process is favorite everybody!

[@Mmmkay..]

This professor's sense of humor is top shelf lol

[@hassanmohammed995]

thank you MIT, god will bless you.

[@philippbecker3117]

Please keep your superstition for yourself.

[@AliM-qr8lq]

@@philippbecker3117 do u feel depressed ? i can tell why..

[@peeedurr]

If you're quick - at around 28:46 you can see on line 165 that he has a case where n == 1. You can't see the code below, but it will be as his slide shows, computing n - 1 and n - 2. So, as he enters 0 (zero), and as his base case of n ==1 doesn't match, he keeps subtracting from n going negative and recurses to death. What I have learned though is that you can have two functions with the exact same signature in a module (who knew!), and that in this case, Python chooses to call the latter one!

[@sagarjadhav1706]

Excellent explanation !!!

[@Xplao123]

Very easy to understand! Thanks

[@PascalThalmann]

great explanation! Thanks!

[@patriotpatriotic3894]

Awesome! Thanks for sharing!

[@infinitasfish5499]

Very entertaining and clear at the same time )

[@kennethkimani7674]

this lecture was pretty fun

[@yuminkim7264]

Nice prof! Thanks

[@solmie3978]

Great Prof! Thank you

[@chilily901]

"after several months, you get to Australia" LOL. Fun and great Professor. Thank you sir!

[@yannickescalera3231]

Awesome lesson!

[@kevin_mitchell]

The lecture states: "With n = 34: 11+ million calls with original fibonacci code, and 65 calls with the efficient dictionary code/" I'm teaching myself c++ and learning recursion (and a little bit of python as well) with this lecture. The version below, without the "efficient dictionary code" does it with 35 calls: def fib(n, temp=1, first=1, next=2): if n == 0: return temp return fib(n-1, first, next, first+next) print(fib(34))

[@fckthosealltrades849]

NICE

[@surajjain7119]

How is it going kevin ?

[@tusharj8588]

Thank you MIT

[@Nevarek_]

Just as a head's up, the recursive algorithm here is known as a head recursion algorithm, which requires a larger space complexity than a tail recursion algorithm. Searching for tail recursion will teach you how to write/rewrite the same algorithm and will remove the necessity to use O(N) stack space. You can see something similar being done using a dictionary to cache return values. And to answer "who cares", embedded and real-time systems programmers care. Game development cares about performance constantly. What he really should have said is "how badly do you need it to be optimized". And he's right, in most cases you won't ever have to care, but you also need to know what happens when you do.

[@akbarrauf2741]

thank you ,mit

[@broswhoknowstuff]

Would inclusion in the lecture of the 'call stack' or Python's symbol table concept help explain recursion? As you recursively call the function object's return value, the frames get 'popped' off the stack (symbol table on Python I think?) Sorry, self-taught. Still learning every day.

[@broswhoknowstuff]

On the fib(x) function for rabbits: def fib(x): if x == 0 or x == 1: return 1 else: fib1 = fib(x-1) fib2 = fib(x-2) return fib1 + fib2 print(fib(0)) // expected 0 I'm sure there is a cleaner way.

[@sibunhill]

Ran into a issue when a supplied argument is zero in both of the first two examples since they only evaluate 1 as the base case. I modified the code and the following seems to work properly. def multiply(a, b): '''Returns a multiplied by b''' if b > 0: return a + multiply(a, b - 1) else: return 0 def factorial(n): '''Returns the factorial of n''' if n > 0: return n * factorial(n - 1) else: return 1

[@jasdeepsingh6568]

I love this dude.

[@calumyoung7172]

thank you. that was very helpful.

[@darshanpatil6892]

I loved that the recursion Fibonacci code(inefficient one) has some flaws for its optimization but I couldn't understand how the modified dictionary becomes the argument for the fibo_efficient(n, d) I mean we modified 'd' but was already given to the fibo_efficient(n, d) as it's an argument? 46:40

[@diegrille6050]

good explanations 👍

[@csvegso]

great teacher

[@hasantaz7832]

Nah man this guy Is undefeated. Too good.

[@rolandgerard6064]

I wish i had such professors....

[@aadway]

I always knew Narendra Modi was a coder in dark.

[@nikhil2021]

LMAO!

[@soumadip_skyy_banerjee]

Lol

[@yashikasaxena4626]

Lmao

[@Krimson5pride]

best comment here

[@aryamahima3]

😂😂😂

[@YoshBruh]

frik I gotta study for that quiz on Thursday

[@yourduck]

I'm a little confused on one point. I understand recursion, but from what I am reading online, most of the time it is more efficient in terms of processing times to write code using an iteration than a recursion. I get that some people might find one more readable than the other and that for many programs, most users wouldn't notice a difference, but wouldn't it be a best practice to normally iterate to make code as efficient as possible?

[@petervan7372]

just learned another polish contribution to cs “how many twists does it take to screw in a light bulb”, apart from polish notation

[@jakeambrose4294]

good teacher

[@sumeetbansal3552]

he really understands what a student is going through.

[@tamojitbasu8634]

As compared to our country where professors or teachers in high schools give a shit about what a student have learnt and what a student is going through except few student friendly teachers and professors. Foreign professors and teachers takes care about every students whether academically poor or brilliant and guides them in a friendly manner which encourages students to learn in a fascinating and practical approach. In our country they give notes writes bullshit on boards copy them and paste it on your exams except few good indian professors and teachers. Even when a student fails foreign professors helps them pointing out his weakness and helps to strong them in a beautiful way and then there's our country if anyone fails they humiliate the student in front of entire class starting from schools to colleges. Sad reality of Indian education system😔

[@adelaidekhayon2631]

any other classes with him?

[@thomaswilburn6263]

thanks mate!

[@dalebada4810]

Thanks! This lecture about recursion was great. Its purpose was well defined and elaborated. Did anyone spot the "code error" regarding the base -case at 46:58 by the way?

[@nicoarellano]

d = {1:1, 2:1} I noticed the same. Anyway, great lecture

[@foreveryoung1678]

Yes, on line 165, had a another fib defined with only a base case n =1. That's why fib(0) bombed as it would just keep going down the rabbit hole.

[@tsuba666]

Not to be overly ungrateful (because I'm not), but I was hoping to see this lecture from professor Ana Bell. I already saw this one from another course, and it seems no matter the professor teaching the course (Pr Guttag or Pr Bell), Pr Grimson is always the one taking care of Recursion. I was hoping to get another explanation, from another source to help me get it, and I do find Pr Bell's way of teaching very clear, very easy to understand.

[@jh0720]

46:58 so what if you want fib_efficient(0, d)?

[@ali51717]

infinite loop error basically, you can add 0:0 to the dictionary as the base case instead of the 2:2 or make them 3 if you have enough bytes on your storage

[@BongelaMnguni]

Very nice

[@peasant7214]

Thanks to Mr. Chinese guy pre labeling ​​0:00:00 0:02:31​ 0:04:00 What is Recursion 0:05:58 Iterative algorithm so far 0:05:58 Multiplication iterative solution 0:07:56 0:09:49 Factorial 0:12:03 Recursive function scope example ​0:13:46​ Some observation 0:16:07 0:18:03 Example of induction 0:19:44 ​​0:23:12 Hanoi tower 0:24:56 ​Recursion with multiple base cases 0:26:14 Fibonacci 0:28:06​ 0:30:23 ​Solving recursively 0:33:52 How to store student info 0:35:45 ​0:36:00 ​0:38:00​ 0:40:25 Dict v.s. List 0:41:52 Creating a dictionary 0:43:02 ​0:44:16 ​0:45:16 ​0:46:25

[@rishabhtripathi6290]

Great version of tower of hanoi... 😀

[@firstyfirst]

How u doin?

[@likesurfs]

There is one mistake. Shouldn't Fib(2) be equal to 1. That is at 46:58 the d should be d = {1:1, 2:1} instead of d = {1:1, 2:2}. Please check.

[@vidieo__]

Because there are 2 different definitions of the Fibonacci numbers. In this case, the Professor uses Fibonacci's original definition, so the sequence starts with 1, i.e. fib(0) = 1. Nowadays people usually start the sequence with 0, or fib(0) = 0. Neither is wrong.

[@pblinfo8531]

Why did Prof. Grimson add k+1 to k(k+1)/2 at 19:07 ?

[@idc20627]

During the mathematical induction step he explained, he said he wants to show that "this is equal to that". I believe the "that" it the k+1 * k+2 ,,," but what is the "this"?

[@sumittripathi1331]

Ah!...he finally found the right glasses. (refer to 6.001 fall 2008)

[@sitrakaforler8696]

Mise en abîme ! ❤

[@nup_pun]

Small typo in slide 38 at 31:00 ; "leba" instead of "elba" was written in the condensed string.

[@robinsir]

Acronyms like PHP are also recursive!

[@NoName-ef2gv]

Does anyone else have the same trouble understanding the Hanoi code at 23:13?

[@abdimajid99]

Me too bro, i couldn't get it

[@sairevanth7126]

How do we initialise variables in recursion in Python so that it continues values in every local scope without it's initial value in global scope?

[@kevin_mitchell]

you can use optional/default values in the parameters for the function e.g. you only need to call the following function with fib(10) - although you have the option of supplying arguments for the optional/default parameters if you want to def fib(n, result=1, first=1, next=2): if n == 0: return result return(n-1, first, next, first+next)

[@abdullahalnoman4249]

32:43

[@user-oy3ok1qd2y]

But I am tenured, you could not do a damn thing about it. LOL, that punchline is fire! Love this professor.

[@kumarjalaj1222]

wow!!!

[@tjtube263]

Hold up. Nice lecture but I'm not satisfied with the solution to the Towers of Hanoi exercise: You changed the rules. That would be the obvious solution, but the premise of the challenge was that the priests could only move one disc at a time (like the river crossing problem). Isn't that the whole point?

[@FullMetal-nu8bj]

I think he is hilarious. Great explanation on recursive frames. Does Australia have a bunny problem...?

[@BlitzN7]

Rabbits have been considered to be a invasive pest for a few decades here in Australia.

[@ryanthackston3439]

en.wikipedia.org/wiki/Rabbits_in_Australia "Various methods in the 20th century have been attempted to control the Australian rabbit population. Conventional methods include shooting rabbits and destroying their warrens, but these had only limited success. In 1907, a rabbit-proof fence was built in Western Australia in an unsuccessful attempt to contain the rabbits. The myxoma virus, which causes myxomatosis, was introduced into the rabbit population in the 1950s and had the effect of severely reducing the rabbit population. However, the survivors have since adapted and partially recovered their previous numbers." Also read the "Biological Measures" section.

[@sujaysyal]

They did him dirty at 16:53

[@Cashman9111]

at 32:30 at the one before the last line shouldn't there be "and isPal(s[1:-2])" , -2 instead of -1 ?

[@ali51717]

when I created my own program before this lecture I actually used that " -2" then I run into errors to realize few things which I will summarize it for you as below 1- when you usually want to last element or the last index we use array[-1] 2-when we use the " [:] " this is calling slicing methods (mentioned in previous lectures of the same course) now if you know about it array =array[start point : end point] ( there is something called advance slicing if you want to check it ) 3- when we want the same array using slicing method we do it as follows array=array[ : ] notice that doing so we leave black it means to start from the same point so if we want to start an element ahead we do array = array[1:] 4- in a similar way if we want the element before the last we do array = [ : -1] 5- combining them array = array [ 1 : -1 ] 6- try not to confuse indexing of array we slicing of an array good luck

[@Cashman9111]

@@ali51717 thanks, I got that after a while :)