Stack Frame and Tail Call recursion in Python

Description:

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:

1. Recursion behind the scenes. [2 min]

2. What are stack and stack frames? [3-4 min]

3. Benchmarking various ways of solving recursive problems: [10-12 min]

   • Naive way
   • Memoization
   • Tail Call optimisation and using it in Python
   • Iterative way

4. JavaScript takeaways [3 min]

5. Q/A

Prerequisites:

Basic knowledge of Python and recursion.

Content URLs:

Talk at PySangamam '18

• https://www.youtube.com/watch?v=lrY3ZimMxLo

Slide deck:

• https://docs.google.com/presentation/d/1YjHVqniL6abvQVkkBGObRpj6BZNsJ8NDAXOdQUJIPU0/edit?usp=sharing

Speaker Info:

Associate Software Engineer at Symantec Corporation working on delivering Norton browser extension. Have been working with Python since last three years to allow himself to be lazy by automating most of the stuff around him. However spends most of his time looking, debugging and writing Javascript at work. Believes in open source and loves developing good-quality software products.

Speaker Links:

• https://varundey.me
  • https://github.com/varundey