Stack Frame and Tail Call recursion in Python
We know that we should avoid recursions wherever possible and that too much recursion is injurious to our codebase. But why is it so? How does compiler works behind the scenes that makes us say that? What if using recursion is the only way to solve the problem? How do we deal in a situation like that? Do we make a trade-off? How do we know our recursive function will be able to run on CPUs across the globe and not cause a stack overflow in a low end CPU?
In this talk, I’ll explain the working of recursion behind the scenes, how compiler treats a recursive function and what causes the infamous
maximum recursion depth exceeded error. Furthermore I’ll take a deep dive explaining Memoization in Python and how it can help in letting your CPU breathe by decreasing time and memory usage. Lastly I’ll explain about about Tail call recursion in Python; how it works, what is the difference between normal Tail call and Python Tail call and what happens behind the scenes when we use it.
Outline of the talk:
Recursion behind the scenes. [2 min]
What are stack and stack frames? [3-4 min]
Benchmarking various ways of solving recursive problems: [10-12 min]
- Naive way
- Tail Call optimisation and using it in Python
- Iterative way
Basic knowledge of Python and recursion.
Talk at PySangamam '18