What is Stack Overflow Really? (40/100 Days of Python)

Day 40 of the “100 Days of Python” blog post series covering stack overflow

Stack overflow is a common software programming error that occurs when a program exceeds the maximum amount of memory that is allocated for its execution. This can happen when a program is written in a way that allows function calls to be repeated indefinitely, leading to a buildup of function calls and data on the call stack. As the stack memory becomes exhausted, a stack overflow error will occur, causing the program to crash or produce unexpected results. This error is especially common in programming languages that use a stack-based model for function calls and data management, such as Python, C, and C++. Understanding the causes and avoiding stack overflow errors are crucial for writing efficient and stable software programs.

Function Call Stack

When working with functions, the program keeps track of their state — what variables were passed to the function, the values of different variables defined inside the function, etc. The whole information about that state is stored in a stack.

There are two operations that are allowed to be performed on a stack — we can add an element on top of a stack, or we can remove the top of the stack. It’s very similar to a stack of plates placed on top of each other. We can remove the top plate, or add another plate on top of the others. We cannot take any plate below the top one as it would crash the whole thing. So, the only two things we can do is add to the top or remove from the top.

A function call stack is a data structure that stores information about the active functions in a program. Whenever a function is called, its information is pushed onto the top of the stack. The information stored can include arguments passed to the function, the location in the code where the function was called, and any local variables declared within the function.

When a function returns, its information is popped off the top of the stack, and the program resumes executing the code that was active before the function call. The function call stack works like a stack of plates, with the most recently added function call on the top, and the least recent at the bottom.

This allows the program to keep track of which functions are active and the state of each function, so it knows where to return control when a function call ends. Consider the following example:

def function1(n):
    if n <= 0:
        return
    else:
        print(f'Function 1 called with n = {n}')
        function2(n - 1)
        print(f'Returning from Function 1 with n = {n}')

def function2(n):
    if n <= 0:
        return
    else:
        print(f'Function 2 called with n = {n}')
        function1(n - 1)
        print(f'Returning from Function 2 with n = {n}')

function1(3)

Calling function1(3) will create the following call stack:

1. function1(3) is called, and its information is pushed onto the top of the stack.
2. function1 prints "Function 1 called with n = 3" and calls function2(2).
3. function2(2) is called, and its information is pushed onto the top of the stack.
4. function2 prints "Function 2 called with n = 2" and calls function1(1).
5. function1(1) is called, and its information is pushed onto the top of the stack.
6. function1 prints "Function 1 called with n = 1" and calls function2(0).
7. function2(0) is called, and its information is pushed onto the top of the stack.
8. function2 encounters the exit condition (n <= 0), and returns. The information for function2(0) is popped off the stack.
9. function1 continues its execution and prints "Returning from Function 1 with n = 1".
10. The information for function1(1) is popped off the stack.
11. function2 continues its execution and prints "Returning from Function 2 with n = 2".
12. The information for function2(2) is popped off the stack.
13. function1 continues its execution and prints "Returning from Function 1 with n = 3".
14. The information for function1(3) is popped off the stack, and the program terminates.

At each point, the call stack only contains information about the active functions, and as each function returns, its information is removed from the stack.

What is Stack Overflow?

Our computers don’t have infinite memory, so each program can operate with some memory allocated for its execution. A stack overflow occurs when a program exceeds the amount of memory that is allocated for its execution. This can occur in different scenarios especially when a function keeps calling itself. This leads to the growth of the call stack and eventually, the stack overflow error.

The error occurs when the stack memory is exhausted and there is no more space to store function calls or local variables. In Python, this error can occur due to several reasons:

1. Recursion depth: When a function calls itself repeatedly, and the conditions to exit the function are not met, the call stack gets filled, which can lead to stack overflow errors.

In some cases, the function can even perform okay for some inputs but result in a stack overflow for others:

def recursive_function(n):
    if n <= 0:
        return 'The End!'
    else:
        return recursive_function(n-1)

recursive_function(10)     # This is okay
recursive_function(10000)  # This will result in stack overflow error

2. Infinite Recursion: If a recursion never terminates, there is a good chance that it will result in a stack overflow error:

def infinite():
    while True:
        infinite()

infinite() # This will result in stack overflow error

3. Large Data Structures: If a program creates large data structures (such as lists, dictionaries, or trees) and calls functions that recursively traverse and manipulate these structures, it can result in a stack overflow error:

def large_data_structure(n, data):
    if n == 10:
        return data
    data = data + (n,)
    return large_data_structure(n + 1, data)

large_data_structure(0, tuple())      # OK -> (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
large_data_structure(-1000, tuple())  # stack overflow

How to Avoid Stack Overflow Errors?

There are several ways to avoid stack overflow in your programs:

1. Use iterative solutions (using loops) instead of recursive solutions where possible. In some cases, iterative solutions can even be faster than recursive ones. This can help reduce the size of the call stack and avoid stack overflow errors.
2. Limit the recursion depth by adding a maximum recursion limit to your code. This can prevent the call stack from growing indefinitely and causing a stack overflow error.
3. Make sure the code actually stops at some point. Add proper exit conditions to your recursive functions. This ensures that the recursion will eventually stop and that the call stack will be cleared.
4. Increase the allowed recursion depth if necessary. This will make sure the functions can be called many times before hitting a maximum recursion depth exceeded error.

The sys.setrecursionlimit function allows you to change the maximum recursion depth in Python. You can use this function to increase the stack size limit, but be aware that this is a global setting and may affect other parts of your program:

import sys
sys.setrecursionlimit(10**6)

So, Python can have stack overflow errors just like other programming languages. A stack overflow can occur in Python when a function recursively calls itself without a proper exit condition, causing the number of function calls on the call stack to grow indefinitely and eventually overflow.

To prevent stack overflow errors in Python, it’s important to ensure that every recursive function has a proper exit condition and doesn’t recurse indefinitely. You can also use iterative solutions instead of recursive solutions, limit the recursion depth, avoid infinite recursion, and monitor the memory usage of your program to ensure that the stack size stays within a certain limit.

What’s next?

• If you found this story valuable, please consider clapping multiple times (this really helps a lot!)
• Hands-on Practice: Free Python Course
• Full series: 100 Days of Python
• Previous topic: Recursion in Python
• Next topic: Regular Expressions