6. Recursion and Dictionaries

[@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!

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

[@鄭心和]

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?

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

[@genealso6726]

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

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

[@DanielFerreira-gu1di]

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

[@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!

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

[@simenghan5897]

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

[@陳矩翰]

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😀

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

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

[@andycalderon8422]

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

[@hdsmsmart]

which course is it ?

[@محمدمصطفى-س9ع]

@@hdsmsmart the same course but on mit platforme

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

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

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

[@mouleeswarkothandaraman7095]

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

[@12EdinAb]

i see what u did there

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

[@androtech7885]

The last two codes went over my head.

[@scorpio19771111]

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

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

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

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

[@boysen01]

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

[@shreyapatel4127]

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

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

[@Mmmkay..]

This professor's sense of humor is top shelf lol

[@manishahatzade1006]

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

[@AnmolKumar-dh3lh]

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

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

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

[@pidusredlah]

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

[@RandomShowerThoughts]

this professor is insanely good at what he does

[@Rogues4Ever]

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

[@FINSuojeluskunta]

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

[@julio1148]

I want this man's presentation skills/confidence

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

[@aadway]

I always knew Narendra Modi was a coder in dark.

[@nikhil2021]

LMAO!

[@soumadip_banerjee]

Lol

[@yashika2701]

Lmao

[@Krimson5pride]

best comment here

[@aryamahima3]

😂😂😂

[@chilily901]

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

[@spyinsecret0075]

I love the professor way of teaching!

[@hasantaz7832]

Nah man this guy Is undefeated. Too good.

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

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

[@ParsaNaderiX]

What an episode! 🔥

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

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

[@user-nq5wb1cz5e]

Great professor

[@alinaust2452]

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

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

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

[@Zedprice]

This guy's explanations don't actually make sense to me. He gets to the exact point where I don't quite get what's happening, and goes "And that's why this works." And I'm like, NO YOU HAVE NOT ACTUALLY EXPLAINED WHY THE RECURSION WORKS IN THIS INSTANCE. He needs to keep going and break it down, but he keeps rushing ahead instead because he has other stuff he apparently wants to talk about. I don't understand his towers of Hanoi code. I don't understand his Fibonacci code. I don't understand the palindrome code. Each time because he just abruptly stops once he reaches the recursion.

[@theodenednew8874]

Zed I was reading these comments and wondering why the hell everyone was applauding this guy for the same reasons you stated. With Ana I felt like she was talking to anyone. She was very easy to understand. This guy on the otherhand, makes me feel like he’s only talking to MIT students. I had to rewatch this multiple times lol

[@ChiNguyen-bc4kt]

In his Towers of Hanoi code, I can figure out the process when n==1 and n==2, but I can't figure out steps in the process when n==3 or more. I think he wants us to think of it recursively: if it is true for smaller versions of the problem, then it is true for the bigger version of the problem and the code turns out to be true when n==3

[@ChiNguyen-bc4kt]

@Ken MacDonald Yeah I know but as n goes up, there will be hundreds of steps. So do they recurse on the other because the same rules still applied?

[@hamzafarooq7864]

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

[@iphoneultra]

thank you MIT

[@TheDoomCompany]

Hard ass concepts fr

[@DingusKhan42]

Excellent lecture and lecturer. Thanks for posting this.

[@RyanScarbrough]

Complex yet really well explained, thanks!

[@kennethkimani7674]

this lecture was pretty fun

[@爱学习-s6k]

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

[@user__unknown]

Fibonacci -> 24:45

[@sujaysyal]

They did him dirty at 16:53

[@petervan7372]

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

[@infinitasfish5499]

Very entertaining and clear at the same time )

[@robinsir]

Acronyms like PHP are also recursive!

[@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😔

[@nup_pun]

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

[@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 :)

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

[@PedramNG]

Wow, this course got hard so fast.

[@peasant7214]

everything is hard until it is broken down.

[@aymensekhri2133]

Thanks a lot Prof. Eric !

[@akbarrauf2741]

thank you ,mit

[@xuanchen3151]

Trust the natural recursion!

[@rishabhtripathi6290]

Great version of tower of hanoi... 😀

[@firstyfirst]

How u doin?

[@sumittripathi1331]

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

[@mohammedabadirleencahararg9974]

nice teacher ur teaching process is favorite everybody!

[@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"?

[@YoshBruh]

frik I gotta study for that quiz on Thursday

[@sitrakaforler8696]

Mise en abîme ! ❤

[@jasdeepsingh6568]

I love this dude.

[@vincenr8822]

Thank you so much. This is amazing.

[@yannickescalera3231]

Awesome lesson!

[@sagarjadhav1706]

Excellent explanation !!!

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

[@yuminkim7264]

Nice prof! Thanks

[@adelaidekhayon2631]

any other classes with him?

[@ashishtrivedi6426]

The Holy amalgation of lookup and recursion called DYNAMIC PROGRAMMING>...................

[@calumyoung7172]

thank you. that was very helpful.

[@pblinfo8531]

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

[@rolandgerard6064]

I wish i had such professors....

[@PascalThalmann]

great explanation! Thanks!

[@Xplao123]

Very easy to understand! Thanks

[@BlackhandYsmira]

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

[@hish3098]

A canadian treasure

[@patriotpatriotic3894]

Awesome! Thanks for sharing!

[@englishmotherfucker1058]

to understand recursion, one must first understand recursion of n-1

[@pinxieanime]

Fibonacci would be extremely proud of you.

[@bobthornton8282]

You can use a list instead of a dictionary and get similar computation times

[@ali51717]

you actually can not, at least to the given problems in the lecture, I tried so already and tested every method and way to make list better than dictionaries in the lecture's examples but, dict. did beat list in that + you are welcome to try

[@caliserion]

good explanations 👍

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

[@aayushsharma2077]

Don't know why MIT kids didn't laugh. His jokes were quite good! :D

[@movesinc]

maybe... just maybe they don't have microphones.

[@spanish1977]

Great Prof! Thank you