Call Stacks - CS50 Shorts
HTML-код
- Опубликовано: 24 янв 2018
- ***
This is CS50, Harvard University's introduction to the intellectual enterprises of computer science and the art of programming.
***
HOW TO SUBSCRIBE
ruclips.net/user/subscription_c...
HOW TO TAKE CS50
edX: cs50.edx.org/
Harvard Extension School: cs50.harvard.edu/extension
Harvard Summer School: cs50.harvard.edu/summer
OpenCourseWare: cs50.harvard.edu/x
HOW TO JOIN CS50 COMMUNITIES
Discord: / discord
Ed: cs50.harvard.edu/x/ed
Facebook Group: / cs50
Faceboook Page: / cs50
GitHub: github.com/cs50
Gitter: gitter.im/cs50/x
Instagram: / cs50
LinkedIn Group: / 7437240
LinkedIn Page: / cs50
Reddit: / cs50
Quora: www.quora.com/topic/CS50
Slack: cs50.edx.org/slack
Snapchat: / cs50
Twitter: / cs50
RUclips: / cs50
HOW TO FOLLOW DAVID J. MALAN
Facebook: / dmalan
GitHub: github.com/dmalan
Instagram: / davidjmalan
LinkedIn: / malan
Quora: www.quora.com/profile/David-J...
Twitter: / davidjmalan
***
CS50 SHOP
cs50.harvardshop.com/
***
LICENSE
CC BY-NC-SA 4.0
Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International Public License
creativecommons.org/licenses/...
David J. Malan
cs.harvard.edu/malan
malan@harvard.edu
Seriously Guys put this video into weeks 3 shorts as an addon to the recursion one, this explains it so good!
Perfect course until right here too! I don't get how they show us that merge sort algorithm then don't tell us how it's working.
I assume we are supposed to learn how to build a merge sort then but no way you can do that without perfect knowledge of the call stack.
@@marketsareopenmao @cs50 Yeah I got stumped in Week 3's Merge sort too. Just happened across this video now so hoping it'll help me progress.
@@GrumpyStoic lol yeah 11 months later I stopped there... I want to get back to it but it took a while to understand merge sort. Then I got too busy to continue.
Good advice.
Yes - for me the recursion short didn't make sense (i.e. HOW does the function know!!) until I saw this. The videos should be merged.
Finally, I got recursion and stack frames after your explanation. Thank you Doug.
Finally I see what is meant by a return.
It makes no sense without the concept of the stack frame.
Finally! I was trying to figure out this exact recursion problem without knowing what a call stack was. Then I saw 'call stack' briefly mentioned on Stack Overflow, did a Google search, found this video, watched it, and saw the light at the end of the tunnel. For a while, I thought I was just not able to grasp recursion and that it was a concept enjoyed by only the most sophisticated intellects...kind of like looking at one of those old 3-dimensional posters that contained a hidden image obscured by garble that could only be revealed if you stared at the poster with the right amount of eye blur, mind shift, or focal point. I never did find the 'knack' for looking at those posters and, before watching this video, I was certain I'd have to dismiss recursion as another one of those things I "just didn't get". This video really helped me out. Recursion might not be so strange after all. Thanks.
I took a CS50 course online and have now decided to do a computer science degree thanks to that course. I always come back to Doug's videos when I need a10/10 explaination. Cheers Doug!!
This was great. I was confused after the Week 3 lecture and still confused after the Recursion video but now I get this principle.
This video was incredibly easy to understand and the concept was very eloquently taught. Thank you, Doug!
Where was this video before? I really needed it? Finally. Easy to understand.
Again, I love these visual examples of functions and the order in which they pop off the top of the stack. This is so helpful!
Amazing! So grateful for your lessons Doug!
Thanks so much Doug!!! The quality of explanation on your videos are superb!!
the way of thinking about this in terms of what is "active" and what is "paused" in the stack is super helpful!
best visual explanation on recursion. I finally understand it. Thank you.
This brought a bunch of concepts together for me. Thanks, Doug!
I FINALLY understand recursion! After so many years! Thank you Doug and CS50!
Thank you very much for this explanation and visualisation!
Such a great video! You explained the call stack so well! thank you Doug.
Doug and his sexy codes lol, that is really all I remember from that recursion video.
That bit was a classic. Love ya Doug you sexy code beast!
Not sexy, it was “seaxy”
Frankly, those Shorts are a knowledge treasure. Thank you David J. Malan, thank you Doug Lloyd, thank Harvard.
Awesome explanation...From the day I learned recursion in data structures and algorithm subject years back, I had this doubt. How the variables are retained in each call and the final output. Today this video gave me the answer...great relief
Thank you, Doug! This is really helpful. I feel like my mind opens and all of a sudden I can understand how everything I've programmed this far works.
Wow this is necessary for understanding recursion in week 3. Thank you for the information.
This and the numberphile explanation (recursion) are the best explanations on the web.
Best Recursion explanation I found in the web! Thanks Doug!
Very nice sir!! This indeed helped a lot. Thank you so much.
I did understand recursion but I invented my own concept about it and you finally made the link between call stack and recursions when I was learning about call stacks. Thank you!
thank you, it's so clear. Help me a lot to understand how recursion works and call stacks
Thank you very much, Doug! It was very intuitive and your explanation was precise and direct. :))
I love you, Doug. Thank you for your explanation. It helps me to become a better person.
This was really great explanation. Very simple easy to follow
Thank you, great work, life saver! Thank you so much!
Doug you are an angel, thank you very much for the explanation.
The first explanation of recursions during all weeks in CS50 what I was able to understand 🙂
You definitely have to change Short name from Call Stacks to Recursions !!!
You're amazing sir.
great explanation Mr. Lloyd
Doug you're the man, dude!
only after this video, I resolved tideman problem from Week 3 problem set. THANKS DOUG
Very well put !
Thank you very much !
This is fantastic, thank you!
Excellent explanation! Thank you.
Very nice, easy to understand explanation! Thank you!
This is so great. Thank you
Incredible explanation! Thank you!
kya baat hai guru maja aa gaya . waah waah waah waah .
If anyone needs a visual explanation; I've wrote it out below. I couldn't understand till I typed everything out, hopefully this helps someone too.
FUNCTION:
int fact(int n)
{
if (n == 1)
return 1;
else
return n * fact(n-1);
}
int main(void)
{
printf("%i
", fact(5));
}
EXPLANATION:
int fact(int 5)
{
does (5 == 1)? no
move to else statement;
else
return 5 * fact(5-1);
[aka: return 5 * fact(4)]
[what is fact(4)? let's find out]
}
int fact(int 4)
{
does (4 == 1)? no
move to else statement;
else
return 4 * fact(4-1);
[aka: return 4 * fact(3)]
[what is fact(3)? let's find out]
}
int fact(int 3)
{
does (3 == 1)? no
move to else statement;
else
return 3 * fact(3-1);
[aka: return 3* fact(2)]
[what is fact(2)? let's find out]
}
int fact(int 2)
{
does (2 == 1)? no
move to else statement;
else
return 2 * fact(2-1);
[aka: return 2 * fact(1)]
[what is fact(1)? let's find out]
}
int fact(int 1)
{
does (1 == 1)? YES
return 1;
else statement not used
}
thus; fact(1) = 1
NOW BACK WE GO BACK!
int fact(int 2)
{
else
return 2 * fact(2-1);
}
return 2 * fact(1)
what is fact(1)? 1
return [2 * 1] = 2
thus; fact(2) = 2
int fact(int 3)
{
else
return 3 * fact(3-1);
}
return 3 * fact(2)
what is fact(2)? 2
return [3 * 2] = 6
thus; fact(3) = 6
int fact(int 4)
{
else
return 4 * fact(4-1);
}
return 4 * fact(3)
what is fact(3)? 6
return [4 * 6] = 24
thus; fact(4) = 24
int fact(int 5)
{
else
return 5 * fact(5-1);
}
return 5 * fact(4)
what is fact(4)? 24
return [5 * 24] = 120
thus; fact(5) = 120
THEREFORE:
printf("%i
", fact(5));
fact(5) = 120
print: 120
thanks for your explanation, I was confused in int fact 4 when he said 4 * 6
Finally understood recursion properly with this explanation!
Thank you very much. It saves me a lot of time.
great visual explanation!
So clear, thank you :)
TY! I feel this is especially important
I finally understand recursion now. from the prior weeks lecture I was like well if its returning 1 when it gets to fact(1), how is it going to solve for the actual value. This should have been in the prior weeks lectures but i understand its a lot to fit in. Thanks
Well explained , Thanks !
You just explained magic to me!
Very clear, thank you
These folks are brilliant! I wonder why this video is excluded from the shorts in week 3?
Awesome, Thanks!!
Great video, very clear explanation, thanks!
Thank you so much for the explanation! I was gonna bang my head against the wall cuz I simply coundn't understand how recursion works in the mario example David wrote. I spent probably more than an hour jumping through hoops trying to make GPT3 explain it, but I simply coudln't make sense of it. Now with 4:30 it all makes sense.
best video on recursion ! thx !
Explained in very easy way tysm.
Really good explanations.
If we give a much bigger value to fact(), will there be a case when the memory contains so much paused fact() frames that the program crashes?
By the way, this is a very helpful video.
yup a stack overflow occurs.
Great presentation. Minor point on this factorial example, it seems that the call stack should also include the 'n' value , n*fact(n-1)
fact(1)
2*fact(1) ---- fact(1)
3*fact(2)---- fact(2)
4*fact(3)---- fact(3)
5*fact(4)----fact(4)
fact(5) ------fact(5)
print() -----print()
main() ---- main()
Very clear explanation!
Small nitpick, printf() should not have a stack frame in this example. Arguments are evaluated first (building on top of the main() frame) and all fact() frames will be removed from the stack before calling printf(). But this is not a big deal at an introductory level :)
CS50 is the best course. I wish I could goto Harvard.
Thanks for grate vedio.
Who will handle this frame creation if we don't have is,
For example general embedded systems
Finally understood why the return 1 in the base case does not end the program.
Thank you ❤️
Thanks a ton !
thank you!
Got a little while before I figured out recursion last week, the clue was what I returned up the stack.
Thank you
Thank you.
As a self though I have the problem understanding recursion. Some say "If you want to learn recursion you have to know recursion". Turns out that to understand recursion, we need to understand how call stacks work. And then the rest is become easy. Thanks
understood. thank you
why isn't this video on lect 3? this gave me so much hard time ! i couldn't understand recursion, and i was so stressed for not understanding it! please put this on lect 3
very helpful!!
I have a question, is this applicable on all callbacks? Or only Ajax calls and set Timeout?
I never saw this kind of explanation. Now recursion is transparent to me like spring water.
Pedantic point, but printf is called AFTER the fact completes. That parameter has to be evaluated before the call enters printf. Then again, been a while since i've done C, so i might be wrong.
Until this short, I thought that I understand what is recursion. Now I understand well.
Oh.. now i understand recursion.Thanks
protip: 3:34 you can remove the else and get the same results. like so...
int fact(int n)
{
if (n == 1)
return 1;
return n * fact(n - 1);
}
Or,
int fact(int n) {
return n == 0 ? 1 : n * fact(n - 1);
}
@@freshlemon101 You mean "n == 1", not 0.
@@exnihilonihilfit6316
I included 0 factorial
You're correct; your version works for factorial 1 and factorial 0. Good job. They completely ignored factorial 0 in this exercise - I guess because they didn't want to deal with explaining why 0 factorial is 1. :)
(and it took me over a year to respond) :]
Wish someone would have just told me that functions work like Magic: the Gathering cards from the start.
how does call stack look like with tail recursion and why does it use less stack memory compared to regular recursion?
I understood recursion functions but still don't fully understand how to implement it instead of an iterative one
GOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOD
so that's why the return type is so important ...OMG..now everything makes sense.
perfect
If I had fact(1 000 000 000), would it be reasonable to iterate values in a loop instead of using recursion? If I use recursion, functions would stack up billion times and occupy a lot of memory, while loop operates inside main(). Which one occupies more space in memory recursion or iteration in a loop method? Which one is faster?
loops is faster and it occupy less space in memory than recursion.
main calls fact(5) which returns then main calls printf(string,result of calling fact(5))
yep, this comment should be on top - fact is called first and printf is called only when all fact calls are done, otherwise there is no parameter to pass to printf
@@AFStimo2 The code is written such that while the fact function is defined, it doesn't come into play until after "int main(void)"
So is this a good way or not a good way to program?
How do I troubleshoot Windows 10 error "new guard page for the stack cannot be created"? I know nothing about programing!
Doug Lloyd is awesome man. 👨🏼🏫
What if a function just call itself and does nothing. After how much time the recursive stack will be full and what is the time after which the prrogram will terminate. please help!
There's not a definite answer to your question. The program will terminate when the function called itself so many times that the stack is full. That is known as a Stack Overflow.
pardon me It's like talking to our processor or is it the ram memory? but please ignore my comment please. just ty for Ur vid 👍!
Where is fact(1) equal to 1 stored? I am missing that concept and can't see how fact(2) knows what fact(1) is.
if (n == 1) { return 1; } is where "fact(1) = 1" is stored. This is called the "base case" in recursion and it's what sets a limit to the number of times recursion happens. The stack builds up from the bottom as fact(5), fact(4) because n is greater than 1 and satisfies the "else" condition ... to fact(1) which is defined as equal to 1 by the if statement. Then each step has an initial value to use: fact (1) = 1 so when fact(2) "pops off" next it can multiply 2 times 1, then fact(3) multiplies 3 * 2, down to fact(5) which returns a value of 120 to printf().
i was just curious how you first learned this??
Hey, I really enjoyed this video, however there is a bug at 3:20 in fact function definition, fact of 0 should be equal to 1.
You are my hero. I waned to die because of not understanding recursion on the week 5