Python Stack Frames and Tail-Call Optimization

Avoiding stack overflow in Python using tail-recursion

Recursion in computer science is a method of problem-solving in which a function calls itself from within its own code. This method is very useful and can be applied to many types of problems, however, it has a limitation. Functions use the stack to keep their local variables, and the stack has a limited size. So if the recursion is too deep you will eventually run out of stack space which is called a stack overflow. However, some compilers implement tail-call optimization, allowing unlimited recursion to occur without stack overflow. In this article, I will first talk about the Python stack frames, and then I will explain the concept of tail-call optimization and show you how it can be implemented in Python.

Stack Frames

Stack is a data structure with a LIFO (Last In First Out) order which has two principal operations:

• push: adds an element to the stack
• pop: removes the most recently added element

So the last element added or pushed to the stack is the first element to be removed or popped. The advantage of using the stack to store data is that memory is managed for you. Reading from and writing to stack is very fast, however, the size of the stack…