Call Stacks - CS50 Shorts

***

This is CS50, Harvard University's introduction to the intellectual enterprises of computer science and the art of programming.

***

HOW TO SUBSCRIBE

HOW TO TAKE CS50

HOW TO JOIN CS50 COMMUNITIES

HOW TO FOLLOW DAVID J. MALAN

***

CS50 SHOP

***

LICENSE

CC BY-NC-SA 4.0
Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International Public License

David J. Malan

[realVertiqo]

Seriously Guys put this video into weeks 3 shorts as an addon to the recursion one, this explains it so good!

[maximbrykov]

Finally, I got recursion and stack frames after your explanation. Thank you Doug.

[thewallstreetjournal]

Finally I see what is meant by a return.
It makes no sense without the concept of the stack frame.

[ricklangston]

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.

[marnierogers]

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

[beaumiffle]

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\n", 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\n", fact(5));
fact(5) = 120
print: 120

[JackyVSO]

This was great. I was confused after the Week 3 lecture and still confused after the Recursion video but now I get this principle.

[shreephadke]

This video was incredibly easy to understand and the concept was very eloquently taught. Thank you, Doug!

[oussamatarhi]

Frankly, those Shorts are a knowledge treasure. Thank you David J. Malan, thank you Doug Lloyd, thank Harvard.

[albinsopaj]

Where was this video before? I really needed it? Finally. Easy to understand.

[davidallsopp]

the way of thinking about this in terms of what is "active" and what is "paused" in the stack is super helpful!

[lb]

best visual explanation on recursion. I finally understand it. Thank you.

[mollyexten]

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!

[DylanRobert]

Wow this is necessary for understanding recursion in week 3. Thank you for the information.

[esjihn]

This and the numberphile explanation (recursion) are the best explanations on the web.

[Hermeticoh]

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.

[maxim]

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

[rdx]

I FINALLY understand recursion! After so many years! Thank you Doug and CS50!

[laurisskraucis]

Amazing! So grateful for your lessons Doug!

[omar]

Best Recursion explanation I found in the web! Thanks Doug!