Tail Call Optimization
HTML-код
- Опубликовано: 13 июл 2024
- We hear about tail calls from time to time in the world of programming, and how they can be optimized for performance. What exactly is that, and how would such optimization work? Today, we take a closer look at tail calls, in addition to a common use case - Tail call recursion!
= Contents Page =
0:00 Introduction
0:42 Contents Page
1:13 Foundation: Code and RAM
1:59 Functions and RAM
2:22 The "Return" Problem
2:57 The Call Stack
4:06 Introduction to Tail Calls
4:39 Need for Tail Call Optimization
5:27 Tail Call Optimization
6:14 Tail Call Recursion
7:14 Benefits of Tail Calls
8:02 Conclusion
= 0612 TV =
0612 TV, a sub-project of NERDfirst.net, is an educational RUclips channel. Started in 2008, we have now covered a wide range of topics, from areas such as Programming, Algorithms and Computing Theories, Computer Graphics, Photography, and Specialized Guides for using software such as FFMPEG, Deshaker, GIMP and more!
Enjoy your stay, and don't hesitate to drop me a comment or a personal message to my inbox =) If you like my work, don't forget to subscribe!
Like what you see? Buy me a coffee → www.nerdfirst.net/donate/
0612 TV Official Writeup: nerdfirst.net/0612tv
More about me: about.me/lcc0612
Official Twitter: / 0612tv
= NERDfirst =
NERDfirst is a project allowing me to go above and beyond RUclips videos into areas like app and game development. It will also contain the official 0612 TV blog and other resources.
Watch this space, and keep your eyes peeled on this channel for more updates! nerdfirst.net/
-----
Disclaimer: Please note that any information is provided on this channel in good faith, but I cannot guarantee 100% accuracy / correctness on all content. Contributors to this channel are not to be held responsible for any possible outcomes from your use of the information.
Unsung YT hero! ✨You're a legend, mate! 👑 One of my favourite videos of yours: Priceless for anyone interested in optimization as long as TCO is implemented in your programming language of choice.
Hello and thank you very much for your comment! Glad you liked the video =)
This is near enough the only effective introduction to this topic on the internet. Thank you!
Hello and thank you very much for your comment! Very happy to be of help :)
Most underrated programming channel I have come across so far! Super clear explanations -- thank you!
Hello and thank you so much for your comment! Glad you like the video and the rest of my work =)
This is the only video I found that best explain the topic!!!
Thx A LOT
Hello and thank you very much for your comment and for the super thanks! Very happy to have been of help =)
Thank you veeeery much for this video!!!! I’ve been seraching all this stuff anywhere, but only your video was that best one which could explain what I wanted exactly. Such a short but very meaningful video, excellent, thank you again:)
You're welcome! Very happy to be of help :)
Great explanation - thank you very much.
You're welcome! Very happy to be of help :)
Just saw your vid from 2014 about serialization. Very concise, and direct, and informative. I originally was searching for what pickling is in Python. You made serialization so easy to understand, that I was able to extract the info and relate it to Python pickle function even though you did not even mention it. Excellent job!
Hello and thank you very much for your comment! Glad you liked my work =D
excellent - Interesting. A good teacher with a good understanding of the topic. Never heard of it but now fully understood.
Hello and thank you very much for your comment! Glad you liked the video =)
Explanation was very clear. Props to you.
Hello and thank you very much for your comment! Very happy to be of help =)
Bruh. This is a fabulous expiration
Hello and thank you very much for your comment! Glad you liked the video =)
Thanks for this awesome content. Great illustrations. Simple is beautiful. All the best. 😊
Hello and thank you very much for your comment! Glad you liked the video =)
Tq for clear explanation.
You're welcome! Very happy to be of help =)
That`s the best explanation on the subject i`ve seen so far. I was watching a couple of videos and yours have the best bottom-up explanation. Only thing i found lacking was some examples with popular recursive functions (like factorial or fibonacci sequence)
Hello and thank you for your comment! Yeah that's a good point. Maybe I can revisit this topic sometime. General patterns and how to convert a regular recursive function into tail recursion bears further explanation.
You are the one. Thank you so much.
You're welcome! Very happy to be of help =)
Thanks for the overview, this is one of those terms I've certainly heard and had a vague familiarity with but this really brought it into focus.
Given the rising popularity of functional composition I can see why being able to optimize deeply nested calls would be a real boon!
Hello and thank you for your comment! Yes, I was in the same position as you, this seemed vaguely familiar but I never looked into it until recently. And yes, it's only because I was delving into functional programming!
Great video. So, if a recursive function is tc optimized, does that mean that stack allocated memory for the function is only allocated once (and reused for all recursive calls)?
Hello and thank you for your comment! This may be implementation-dependent, but yes, that's the idea - Either repeatedly reuse or construct and destroy one call stack entry - As long as the entries don't stack up and "wait" for each other, you'll reap the benefits of the tail call.
what software do you use to make your animations/powerpoint slides?
Hello and thank you for your comment! All animations in this video were made in PowerPoint.
What would the memory complexity be?
Hello and thank you for your comment! This one is not so easy to discuss in a vacuum, without knowing what code was written in the function(s) involved. Having said that, the short answer is - The memory usage should be similar to if the program was written as iteration, using loops.
For certain algorithms that, say, pass arrays around and duplicate them for each recursive call, this could mean space complexity improvements from O(n) or more to O(1), while certain algorithms may not have any space complexity benefits at all.
Still unclear to me why you wouldn't have 25 call stacks in memory if you did recursion 25 times..I guess they are just clearing out local variables and the call stack early, is that it?
Hello and thank you for your comment! Assuming that tail call _optimization_ is indeed happening, then yes, the call stack entries can be overwritten or deleted once each instance of the function has finished running. You only need to keep track of how to return to the original code that called the function.