*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

3 жыл бұрын

Thank you so much! Ignore the racist!

@leixun

3 жыл бұрын

Emma Go thank you so much!

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

@MrFaiqueShakil

4 жыл бұрын

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

@Tintak_hatpin

4 жыл бұрын

@@MrFaiqueShakil hahaha

@peterpace3379

3 жыл бұрын

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

@snamburi3

3 жыл бұрын

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

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

@georgikostov6982

3 жыл бұрын

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

@obli8984

2 жыл бұрын

that's what I also thought😀

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

4 жыл бұрын

because its not a funny "joke"

@stephenc9398

4 жыл бұрын

@@RocknRollDina You are a funny joke

@RocknRollDina

4 жыл бұрын

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

@federicofraguglia6773

4 жыл бұрын

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

@Raghav1205

4 жыл бұрын

Because there is no base case

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

@wanyinleung912

5 жыл бұрын

And the third thing is all cs jokes are bad.

@gold9994

4 жыл бұрын

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

3 жыл бұрын

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

@cybern9ne

2 жыл бұрын

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

@changding4355

2 жыл бұрын

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

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

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.

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

2 жыл бұрын

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

6 ай бұрын

@@ChandravijayAgrawal

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

@12EdinAb

Жыл бұрын

i see what u did there

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

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

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.

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 KZread are great, too! Thank you Professor and MIT!

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

2 жыл бұрын

NICE

@surajjain7119

2 жыл бұрын

How is it going kevin ?

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?

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

The last two codes went over my head.

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

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

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

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

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.

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.

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

@hdsmsmart

3 жыл бұрын

which course is it ?

@user-kv8oh8lx7y

2 жыл бұрын

@@hdsmsmart the same course but on mit platforme

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.

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

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!

Complex yet really well explained, thanks!

I love the professor way of teaching!

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

@vu_derArchitekt

5 жыл бұрын

Hanoi Tower not Hanna :)

@yukeyang5735

5 жыл бұрын

You're right.Thanks for the correction.

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

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

Excellent lecture and lecturer. Thanks for posting this.

I want this man's presentation skills/confidence

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

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

this professor is insanely good at what he does

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.

Thanks a lot Prof. Eric !

Great professor

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

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

nice teacher ur teaching process is favorite everybody!

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.

great explanation! Thanks!

Thank you so much. This is amazing.

Awesome! Thanks for sharing!

thank you MIT, god will bless you.

@philippbecker3117

6 жыл бұрын

Please keep your superstition for yourself.

@AliM-qr8lq

4 жыл бұрын

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

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

Excellent explanation !!!

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.

Very easy to understand! Thanks

I always knew Narendra Modi was a coder in dark.

@nikhil2021

6 жыл бұрын

LMAO!

@soumadip_skyy_banerjee

6 жыл бұрын

Lol

@yashikasaxena4626

5 жыл бұрын

Lmao

@Krimson5pride

5 жыл бұрын

best comment here

@aryamahima3

4 жыл бұрын

😂😂😂

Nice prof! Thanks

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

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

@TheVertical92

3 жыл бұрын

check out CS50 from Havard.

@kenmeyer100

3 жыл бұрын

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

@xXZian6Xx

3 жыл бұрын

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

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

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__

2 жыл бұрын

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.

Great Prof! Thank you

Awesome lesson!

thank you MIT

Very entertaining and clear at the same time )

this lecture was pretty fun

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

any other classes with him?

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?

thank you. that was very helpful.

This professor's sense of humor is top shelf lol

good explanations 👍

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

great teacher

Thank you MIT

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

3 жыл бұрын

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

@foreveryoung1678

2 жыл бұрын

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.

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

thank you ,mit

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

@abdimajid99

3 жыл бұрын

Me too bro, i couldn't get it

I love this dude.

Nah man this guy Is undefeated. Too good.

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

I wish i had such professors....

good teacher

Very nice

frik I gotta study for that quiz on Thursday

thanks mate!

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

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

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

@ali51717

5 жыл бұрын

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

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.

They did him dirty at 16:53

Great version of tower of hanoi... 😀

@firstyfirst

3 жыл бұрын

How u doin?

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

@ali51717

5 жыл бұрын

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

5 жыл бұрын

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

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

3 жыл бұрын

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)

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

@ali51717

5 жыл бұрын

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

Acronyms like PHP are also recursive!

he really understands what a student is going through.

@tamojitbasu8634

3 жыл бұрын

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😔

32:43

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

Shouldn't there be 2 cases for the factorial function? if n==1 or n==0: return 1

@UtkarshShah12

7 жыл бұрын

Only n==0 should suffice, as 1!=1*0!=1

@abhishektanwar8576

6 жыл бұрын

yeah. these two cases are for fibonacci series

@aravindsairam3432

6 жыл бұрын

Yes there can be. But, they don't make the code any efficient so they would have not mentioned that.

@saurabh75prakash

6 жыл бұрын

One can think n==0 as base case. Which was not considered as it is preceded by n==0 base case in the lecture. One can re-write code assuming n==0 as base case.

@sibunhill

5 жыл бұрын

def factorial(n): '''Returns the factorial of n''' if n > 0: return n * factorial(n - 1) else: return 1

i was not able to understand the code at 45:16 can any one help

I like this